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]
最少移动次数使数组元素相等II。
题意跟版本一很接近，但是这次并不是将所有的数字都往最大值靠拢，这个题考的是问最少操作多少次可以使所有数字相同，而且这个题的操作次数是针对每一个数字而言的，也就是说，每一个数字动一次，就是一次操作。
思路是找到数组的中位数，然后每个数字和中位数的差值就是操作次数。最后要求的结果就是每个数字的操作次数的累加和。既然是求中位数，比较直观的思路就是用Arrays.sort()先排序，找到数组中间的数字，或者是用快速排序找。就这道题的test case而言，前者更快。
时间O(nlogn), worse case is O(n^2)
空间O(1)
Java函数排序
1 class Solution {
2 public int minMoves2(int[] nums) {
3 Arrays.sort(nums);
4 int res = 0;
5 int mid = nums[nums.length / 2];
6 for (int num : nums) {
7 res += Math.abs(num - mid);
8 }
9 return res;
10 }
11 }
快速排序
1 class Solution {
2 public int minMoves2(int[] nums) {
3 int res = 0;
4 int median = findKthLargest(nums, nums.length / 2 + 1);
5 for (int num : nums) {
6 res += Math.abs(median - num);
7 }
8 return res;
9 }
10
11 private int findKthLargest(int[] nums, int k) {
12 if (nums == null || nums.length == 0) {
13 return 0;
14 }
15 int left = 0;
16 int right = nums.length - 1;
17 while (true) {
18 int pos = partition(nums, left, right);
19 if (pos + 1 == k) {
20 return nums[pos];
21 } else if (pos + 1 > k) {
22 right = pos - 1;
23 } else {
24 left = pos + 1;
25 }
26 }
27 }
28
29 private int partition(int[] nums, int left, int right) {
30 int pivot = nums[left];
31 int l = left + 1;
32 int r = right;
33 while (l <= r) {
34 if (nums[l] < pivot && nums[r] > pivot) {
35 swap(nums, l++, r--);
36 }
37 if (nums[l] >= pivot) {
38 l++;
39 }
40 if (nums[r] <= pivot) {
41 r--;
42 }
43 }
44 swap(nums, left, r);
45 return r;
46 }
47
48 private void swap(int[] nums, int i, int j) {
49 int temp = nums[i];
50 nums[i] = nums[j];
51 nums[j] = temp;
52 }
53 }