如果我們可以增加/減少一個特定的數組元素，最小總移動數量爲1

Question

這是代碼462. 我有一個算法，但是在傳遞其他數據時失敗了一些測試。 我試圖通過但不知道什麼是我忽視的角落案件。我們有一個由N個元素組成的數組。一種移動被定義爲增加或減少數組中的一個單一元素1.我們試圖找到使所有元素相等的最小移動次數。

我的想法是：1。 發現平均 2.最近發現的元素平均 3.總和在一起，每個元素和最接近平均值的元素之間的差異。 我錯過了什麼？請提供一個反例。

class Solution { 
public: 
    int minMoves2(vector<int>& nums) { 
     int sum=0; 
     for(int i=0;i<nums.size();i++){ 
      sum += nums[i]; 
     } 
     double avg = (double) sum/nums.size(); 
     int min = nums[0]; 
     int index =0 ; 
     for(int i=0;i<nums.size();i++){ 
      if(abs(nums[i]-avg) <= abs(min - avg)){ 
       min = nums[i]; 
       index = i; 
      } 
     } 
     sum=0; 
     for(int i=0;i<nums.size();i++){ 
      sum += abs(min - nums[i]); 
     } 
     return sum; 
    } 
}; 

Answer 1

假設數組爲[1,1,10,20,100]。平均有點超過20.所以你的解決方案將涉及19 + 19 + 10 + 0 + 80移動= 128.如果我們的目標是10，那該怎麼辦？那麼我們有9 + 9 + 0 + 10 + 90移動= 118.所以這是一個反例。

假設您決定將所有數組元素更改爲某個值T.問題是，T的正確值是什麼？考慮到T的一些價值，我們可以問T是否增加或減少T會改善或惡化我們的結果。如果我們將T減1，那麼大於T的所有值都需要額外的移動，而所有下面的移動需要一個移動。這意味着，如果T高於中位數，那麼它下面的值比上面的值更多，所以我們從T減少中受益。如果T小於中位數，我們可以做出相反的論證。由此我們可以得出結論：T的正確值實際上就是中位數本身，我的例子證明了這一點（嚴格來說，當你有一個尺寸均勻的數組時，T可以在兩個中間元素之間的任何位置）。