對於一個任務,我需要解決一個數學問題。我縮小到以下內容:尋找A [i]和常數之差的最小總和
讓A[1, ... ,n]
是整數的一個數組。n
整數。
讓y
是一個整數常量。
現在,我必須編寫發現的最小的M(y)
在O(n)
時間的算法:
M(y) = Sum |A[i] - y|, i = 1 to n
。請注意,我不只是採取A[i] - y
,但絕對值|A[i] - y|
。
爲了清楚起見,我也把這個方程式放在Wolfram Alpha。
我已經考慮了最小二乘法,但是這不會產生最小值M(y)
,但我認爲更多的是平均值A
。由於我的絕對值爲A[i] - y
,我也無法將此功能區分爲y
。此外,我不能只是想出任何算法,因爲我必須在O(n)
時間內完成。另外,我相信在某些情況下y
可能會有更多正確的答案,在這種情況下,y
的值必須等於A
的整數元素之一。
這真的一直在吃我整整一週,我還沒有想出來。任何人都可以請教我走的路或指向正確的方向嗎?我卡住了。非常感謝你的幫助。
您正在尋找中位數。我將在一個答案中展示它。 – Nelfeal
@Nelxiost是對的。將'y'設置爲'A'的中位數將導致最小值'M(y)'。您可以在線性時間內計算中位數*中位數*。 –
非常感謝!但是,我將如何能夠證明這種方法? – Anteino