# 0462. Minimum Moves to Equal Array Elements II
###### tags: `Leetcode` `Microsoft` `Medium` `QuickSort`
Link: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
## 思路
找中位数
直接排序或者快速排序
## Code
### 直接排序

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            res += Math.abs(nums[i]-nums[nums.length/2]);
        }
        return res;
    }
}

### 快速排序
**注意：一个看了很久的bug是第17行我原本写的是ans = partition(nums, start, ans-1), 这个不对的原因是在整个quicksort的过程中我用的是左闭右开区间（也就是从头开始就是[0,nums.length)，但第17行原本的想法就以为着我把它当成闭区间了，显然错了**

class Solution {
    public int minMoves2(int[] nums) {
        quickSort(nums, 0, nums.length, nums.length/2);
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            res += Math.abs(nums[i]-nums[nums.length/2]);
        }
        return res;
    }
    public void quickSort(int[] nums, int start, int end, int target){
        int ans = partition(nums, start, end);
        while(ans!=target){
            if(ans<target){
                ans = partition(nums, ans+1, end);
            }
            else{
                ans = partition(nums, start, ans);
            }
        }
    }
    public int partition(int[] nums, int start, int end){
        int p = new Random().nextInt(end-start)+start;
        swap(nums, p, start);
        int idx = start;
        for(int i = start+1; i < end;i++){
            if(nums[i]<nums[start]){
                swap(nums, i, ++idx);
            }
        }
        swap(nums, start, idx);
        return idx;
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}