原题链接在这里：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]
题解：
用quick sort找到median. 类似Kth Largest Element in an Array. 每一个元素对于median差值的绝对值的总和就是最小moves. 这里的median可以理解为第nums.length/2小的element.
Time Complexity: O(n), quick sort O(n).
Space: O(1).
AC Java:
1 public class Solution { 2 public int minMoves2(int[] nums) { 3 int moves = 0; 4 int median = findK(nums, nums.length/2, 0, nums.length-1); 5 for(int num : nums){ 6 moves += Math.abs(num-median); 7 } 8 return moves; 9 } 10 11 private int findK(int [] nums, int k, int start, int end){ 12 if(start >= end){ 13 return nums[start]; 14 } 15 int m = partition(nums, start, end); 16 if(m == k){ 17 return nums[m]; 18 }else if(m < k){ 19 return findK(nums, k, m+1, end); 20 }else{ 21 return findK(nums, k, start, m-1); 22 } 23 } 24 25 private int partition(int [] nums, int start, int end){ 26 int pivot = nums[start]; 27 int m = start; 28 int n = start + 1; 29 while(n <= end){ 30 if(nums[n] < pivot){ 31 swap(nums, ++m, n); 32 } 33 n++; 34 } 35 swap(nums, start, m); 36 return m; 37 } 38 39 private void swap(int [] nums, int i, int j){ 40 int temp = nums[i]; 41 nums[i] = nums[j]; 42 nums[j] = temp; 43 } 44 }
类似Minimum Moves to Equal Array Elements.
LeetCode Minimum Moves to Equal Array Elements II
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/6258762.html