木又连续日更第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-最小移动次数使数组元素相等