如果我们可以增加/减少一个特定的数组元素，最小总移动数量为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可以在两个中间元素之间的任何位置）。