Question

462. Minimum Moves to Equal Array Elements II

中文文档

Description

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.

Test cases are designed so that the answer will fit in a 32-bit integer.

 

Example 1:

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]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

 

Constraints:

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solutions

Solution 1

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    nums.sort()
    k = nums[len(nums) >> 1]
    return sum(abs(v - k) for v in nums)

class Solution {
  public int minMoves2(int[] nums) {
    Arrays.sort(nums);
    int k = nums[nums.length >> 1];
    int ans = 0;
    for (int v : nums) {
      ans += Math.abs(v - k);
    }
    return ans;
  }
}

class Solution {
public:
  int minMoves2(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int k = nums[nums.size() >> 1];
    int ans = 0;
    for (int& v : nums) ans += abs(v - k);
    return ans;
  }
};

func minMoves2(nums []int) int {
  sort.Ints(nums)
  k := nums[len(nums)>>1]
  ans := 0
  for _, v := range nums {
    ans += abs(v - k)
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function minMoves2(nums: number[]): number {
  nums.sort((a, b) => a - b);
  const mid = nums[nums.length >> 1];
  return nums.reduce((r, v) => r + Math.abs(v - mid), 0);
}

impl Solution {
  pub fn min_moves2(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let mid = nums[nums.len() / 2];
    let mut res = 0;
    for num in nums.iter() {
      res += (num - mid).abs();
    }
    res
  }
}

Solution 2

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    def move(i):
      v = nums[i]
      a = v * i - s[i]
      b = s[-1] - s[i + 1] - v * (n - i - 1)
      return a + b

    nums.sort()
    s = [0] + list(accumulate(nums))
    n = len(nums)
    return min(move(i) for i in range(n))