Skip to content

462. Minimum Moves to Equal Array Elements II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  int minMoves2(vector<int>& nums) {
    const int n = nums.size();
    nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
    const int median = nums[n / 2];
    return accumulate(nums.begin(), nums.end(), 0, [&](int subtotal, int num) {
      return subtotal + abs(num - median);
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int minMoves2(int[] nums) {
    final int n = nums.length;
    final int median = quickSelect(nums, 0, n - 1, (n + 1) / 2);
    int ans = 0;

    for (final int num : nums)
      ans += Math.abs(num - median);

    return ans;
  }

  private int quickSelect(int[] nums, int l, int r, int k) {
    final int randIndex = new Random().nextInt(r - l + 1) + l;
    swap(nums, randIndex, r);
    final int pivot = nums[r];

    int nextSwapped = l;
    for (int i = l; i < r; ++i)
      if (nums[i] <= pivot)
        swap(nums, nextSwapped++, i);
    swap(nums, nextSwapped, r);

    final int count = nextSwapped - l + 1;
    if (count == k)
      return nums[nextSwapped];
    if (count > k)
      return quickSelect(nums, l, nextSwapped - 1, k);
    return quickSelect(nums, nextSwapped + 1, r, k - count);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

1
2
3
4
5
6
7
import statistics


class Solution:
  def minMoves2(self, nums: list[int]) -> int:
    median = int(statistics.median(nums))
    return sum(abs(num - median) for num in nums)