当前位置: 代码迷 >> 综合 >> LeetCode 462.最少移动次数使数组元素相等II
  详细解决方案

LeetCode 462.最少移动次数使数组元素相等II

热度:44   发布时间:2023-10-21 03:02:57.0

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

例如:

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

 

我们要找到能够让大家移动次数最少的数字,这个数字一定在最大到最小的数字之间。

假设为数字i,最大的数字a,和最小数字b,需要移动的次数总和=(a-i)+(i-b)=a-b

倒数第二大的数字,和第二小的数字也是如此。

所以最中间的数字是我们要找的数字。

如果nums长度为奇数,就是找中位数。如果nums长度为偶数,就找中间两个数字的平均数。

class Solution:def minMoves2(self, nums):""":type nums: List[int]:rtype: int"""nums.sort()middle=int(len(nums)/2)count=0for i in range(middle):count=count+(nums[len(nums)-1-i]-nums[i])return count