LeetCode: 462. Minimum Moves to Equal Array Elements II

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

462. Minimum Moves to Equal Array Elements II

LeetCode - Minimum Moves to Equal Array Elements II

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example:

Input:
[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]

没想到这里竟然还可以用上快速排序中的变体：快速选择！

相关问题请看： 215. Kth Largest Element in an Array。

 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
38
39
/**
 * 参考 https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solutions/1501230/zui-shao-yi-dong-ci-shu-shi-shu-zu-yuan-xt3r2/[462. 最小操作次数使数组元素相等 II - 官方题解^]。
 */
public int minMoves2(int[] nums) {
  int size = nums.length;
  int mid = quickSelect(nums, 0, size - 1, size / 2);
  int result = 0;
  for (int i = 0; i < size; i++) {
    result += Math.abs(nums[i] - mid);
  }
  return result;
}

private int quickSelect(int[] nums, int left, int right, int index) {
  if (left == right) {
    return nums[index];
  }
  int l = left - 1;
  int r = right + 1;
  int num = nums[left];
  while (l < r) {
    do {
      l++;
    } while (nums[l] < num);
    do {
      r--;
    } while (num < nums[r]);
    if (l < r) {
      int temp = nums[l];
      nums[l] = nums[r];
      nums[r] = temp;
    }
  }
  if (index <= r) {
    return quickSelect(nums, left, r, index);
  } else {
    return quickSelect(nums, r + 1, right, index);
  }
}