0%

leetcode462 Minimum Moves to Equal Array Elements II 解题报告

英文原题

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Example

1
2
3
4
5
Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]

分析

    一道数学题,要求到到所有数距离最小的数那就是中位数。

python 代码

最直接的办法:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def minMoves2(self, nums: List[int]) -> int:
n = len(nums)
mid = 0
nums.sort()
if n % 2 == 0:
mid = (nums[n//2] + nums[n//2-1]) // 2
else:
mid = nums[n//2]

return sum(abs(nums[i] - mid) for i in range(n))

还可以计算头尾两数相差之和,一个道理,”~”是取反。

1
2
3
4
5
class Solution:
def minMoves2(self, nums: List[int]) -> int:
nums.sort()

return sum([nums[~i]-nums[i] for i in range(len(nums)//2)])