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:
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]
2. Implementation
(1) Sort + Two Pointers
思路: 给定两个点A和B, 如果要在它们之间找到一个点C，算出AC和CB的距离，可知Dist(AC): c - a, Dist(CB): b - c, 距离和为 b -a,
所以C点具体在哪不影响结果
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int start = 0, end = nums.length - 1;
int moves = 0;
while (start < end) {
moves += nums[end] - nums[start];
++start;
--end;
}
return moves;
}
}
(2) Quick Select to Get Median
class Solution {
public int minMoves2(int[] nums) {
int n = nums.length;
int median = quickSelect(nums, 0, n - 1, n/2);
int moves = 0;
for (int num : nums) {
moves += Math.abs(num - median);
}
return moves;
}
public int quickSelect(int[] nums, int start, int end, int k) {
int pivot = partition(nums, start, end);
if (pivot < k) {
return quickSelect(nums, pivot + 1, end, k);
}
else if (pivot > k) {
return quickSelect(nums, start, pivot - 1, k);
}
else {
return nums[pivot];
}
}
public int partition(int[] nums, int start, int end) {
int mid = start + (end - start) / 2;
swap(nums, mid, end);
for (int i = start; i < end; i++) {
if (nums[i] < nums[end]) {
swap(nums, i, start);
++start;
}
}
swap(nums, start, end);
return start;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
3. Time & Space Complexity
Sort + Two Pointers：时间复杂度O(nlogn), 空间复杂度O(1)
Quick Select to Get Median: 时间复杂度O(n), 空间复杂度O(logn), 因为quickSelect用了递归