462 Minimum Moves to Equal Array Elements II

1. Question

Given anon-emptyinteger 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:
1
Input: [1,2,3]
2
3
Output: 2
4
5
Explanation:
6
7
Only two moves are needed (remember each move increments or decrements one element):
8
[1,2,3] => [2,2,3] => [2,2,2]
Copied!

2. Implementation

(1) Sort + Two Pointers
思路: 给定两个点A和B, 如果要在它们之间找到一个点C,算出AC和CB的距离,可知Dist(AC): c - a, Dist(CB): b - c, 距离和为 b -a,
所以C点具体在哪不影响结果
1
class Solution {
2
public int minMoves2(int[] nums) {
3
Arrays.sort(nums);
4
5
int start = 0, end = nums.length - 1;
6
int moves = 0;
7
8
while (start < end) {
9
moves += nums[end] - nums[start];
10
++start;
11
--end;
12
}
13
return moves;
14
}
15
}
Copied!
(2) Quick Select to Get Median
1
class Solution {
2
public int minMoves2(int[] nums) {
3
int n = nums.length;
4
int median = quickSelect(nums, 0, n - 1, n/2);
5
int moves = 0;
6
7
for (int num : nums) {
8
moves += Math.abs(num - median);
9
}
10
return moves;
11
}
12
13
public int quickSelect(int[] nums, int start, int end, int k) {
14
int pivot = partition(nums, start, end);
15
16
if (pivot < k) {
17
return quickSelect(nums, pivot + 1, end, k);
18
}
19
else if (pivot > k) {
20
return quickSelect(nums, start, pivot - 1, k);
21
}
22
else {
23
return nums[pivot];
24
}
25
}
26
27
public int partition(int[] nums, int start, int end) {
28
int mid = start + (end - start) / 2;
29
swap(nums, mid, end);
30
31
for (int i = start; i < end; i++) {
32
if (nums[i] < nums[end]) {
33
swap(nums, i, start);
34
++start;
35
}
36
}
37
38
swap(nums, start, end);
39
return start;
40
}
41
42
public void swap(int[] nums, int i, int j) {
43
int temp = nums[i];
44
nums[i] = nums[j];
45
nums[j] = temp;
46
}
47
}
Copied!

3. Time & Space Complexity

Sort + Two Pointers:时间复杂度O(nlogn), 空间复杂度O(1)
Quick Select to Get Median: 时间复杂度O(n), 空间复杂度O(logn), 因为quickSelect用了递归