【leetcode刷题】T202-最少移动次数使数组元素相等 II

木又连续日更第68天（68/100）

木又的第202篇leetcode解题报告

数学类型第18篇解题报告

leetcode第462题：最少移动次数使数组元素相等 II

https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii/

【题目】

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。您可以假设数组的长度最多为10000。

例如:
输入:
[1,2,3]
输出:
2
说明：
只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

【思路】

能想出这道题数学解法的人很牛逼！

很明显，我们应该找数组中间的某个数，然后计算移动步骤。

我们首先想到是平均数，不过好像不对，平均数很可能不是整数，需要处理；另外，好像结果并不是最小值。

其实，我们就是求解：min(abs(nums[0] - x) + abs(nums[1] - x) +… + abs(nums[n-1] - x))

那么，x应该是中位数。（我也不知道怎么解出来的【笑哭】）

我们可以从中位数推出最小值：

假设数组元素个数是奇数2n+1，那么大于中位数的有n个，这些数移动到中位数需要x步；小于中位数的有n个，这些数移动到中位数需要y步。那么总的移动步数为x+y步。如果不是中位数，比如中位数-1，那么大于中位数的，需要移动x+n步，小于中位数的，至少需要移动y-n步（有的数可能大于中位数-1），总的步数大于x+y步。

假设数组元素个数是偶数，只要是两个中位数之间的数，都可以作为移动后的值。因为，如果小于中位数m1的数全部移动到m1，大于中位数m2(m2>=m1)的数全部移动到买m2，那么只要目标值在m1->m2之间，总的移动步数是确定的。

【代码】

python版本

class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        target = nums[len(nums) // 2]
        return sum(map(lambda x: abs(x - target), nums))

C++版本

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int target = nums[nums.size() / 2];
        int sum = 0;
        for (auto n : nums){
            sum += abs(n - target);
        }
        return sum;
    }
};

前一篇文章：T201-最小移动次数使数组元素相等