尋找A [i]和常數之差的最小總和

Question

對於一個任務，我需要解決一個數學問題。我縮小到以下內容：

讓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的整數元素之一。

這真的一直在吃我整整一週，我還沒有想出來。任何人都可以請教我走的路或指向正確的方向嗎？我卡住了。非常感謝你的幫助。

Answer 1

你想選擇一個y，其中M(y) = sum(abs(A[i] - y))是最小的。我們假設每個A[i]都是正數（它不會改變結果，因爲問題是翻譯不變的）。

讓我們從兩個簡單的觀察開始。首先，如果選擇y，使得y < min(A)或y > max(A)，那麼對於M（y），最終得到的值比選擇y時的值大min(A) <= y <= max(A)。另外，A（M（y）是凸的）的極小值的唯一局部最小值或範圍是唯一的。

所以我們可以從間隔[min(A) .. max(A)]中選取一些y開始，嘗試移動這個值以便我們得到一個更小的M（y）。爲了讓事情更容易理解，讓我們排序A並在[1 .. n]（如此y = A[i]）中選擇我。

有三種情況需要考慮。

如果A[i+1] > A[i]，並且{n是奇數並且i < (n+1)/2}或{n是偶數並且i < n/2}，那麼M(A[i+1]) < M(A[i])。
這是因爲，從M(A[i])到M(A[i+1])，減少的術語數（即n-i）大於增加的術語數（即i），並且增加或減少總是相同的數量。在n爲奇數的情況下，i < (n+1)/2 <=> 2*i < n+1 <=> 2*i < n，因爲2 * i是偶數（因此必然小於從中減去1的較大偶數）。
更正式的說法，M(A[i]) = sum(A[i]-A[s]) + sum(A[g]-A[i])，其中s和g代表A[s] < A[i]和A[g] > A[i]的指數。所以如果A[i+1] > A[i]，那麼M(A[i+1]) = sum(A[i]-A[s]) + i*(A[i+1]-A[i]) + sum(A[g]-A[i]) - (n-i)*(A[i+1]-A[i]) = M(A[i]) + (2*i-n)*(A[i+1]-A[i])。由於2*i < n和A[i+1] > A[i]，(2*i-n)*(A[i+1]-A[i]) < 0，所以M(A[i+1]) < M(A[i])。

同樣，如果A[i-1] < A[i]，並且或者{n爲奇數和i > (n+1)/2}或{n爲偶數和i > (n/2)+1}，然後M(A[i-1]) > M(A[i])。最後，如果{n是奇數並且i = (n+1)/2}或者{n是偶數並且i = (n/2) or (n/2)+1}，那麼你有一個最小值，因爲遞減或遞增我將最終分別引導你到第一或第二種情況。對於我來說剩下的可能的價值，但所有這些都導致A [i]也是最小的。

A的中位數正好是我在滿足最後一種情況下的值A [i]。如果A中元素的數量是奇數，那麼您恰好有一個這樣的值，y = A[(n+1)/2]（但可能有多個索引）;如果它是偶數，那麼你有一個範圍（可能只包含一個整數）的這樣的值，A[n/2] <= y <= A[n/2+1]。

有一個標準的C++算法可以幫助您找到O（n）時間的中位數：nth_element。如果您使用的是其他語言，請查找the median of medians algorithm（其中Nico Schertler pointed out）或甚至introselect（這是nth_element通常使用的內容）。