原题链接在这里：https://leetcode.com/problems/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]
题解：
The median minimizes the sum of absolute deviations. There is an article explaining this.
用quick sort找到median. 类似Kth Largest Element in an Array.
每一个元素对于median差值的绝对值的总和就是最小moves. 这里的median可以理解为第nums.length/2小的element.
Time Complexity: O(n), quick select O(n). n = nums.length.
Space: O(1).
AC Java:
class Solution {
public int minMoves2(int[] nums) {
if(nums == null || nums.length < 2){
return 0;
}
int n = nums.length;
int median = findK(nums, (n - 1) / 2, 0, n - 1);
int res = 0;
for(int num : nums){
res += Math.abs(num - median);
}
return res;
}
private int findK(int [] nums, int k, int l, int r){
if(l >= r){
return nums[l];
}
int m = partition(nums, l, r);
if(m == k){
return nums[k];
}else if(m < k){
return findK(nums, k, m + 1, r);
}else{
return findK(nums, k, l, m - 1);
}
}
private int partition(int [] nums, int l, int r){
int pivot = nums[l];
while(l < r){
while(l < r && nums[r] >= pivot){
r--;
}
nums[l] = nums[r];
while(l < r && nums[l] <= pivot){
l++;
}
nums[r] = nums[l];
}
nums[l] = pivot;
return l;
}
}
类似Minimum Moves to Equal Array Elements, Best Meeting Point.