> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/sort/462-minimum-moves-to-equal-array-elements-ii.md).

# 462 Minimum Moves to Equal Array Elements II

## 462. [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/description/)

## 1. Question

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]
```

## 2. Implementation

**(1) Sort + Two Pointers**

思路: 给定两个点A和B, 如果要在它们之间找到一个点C，算出AC和CB的距离，可知Dist(AC): c - a, Dist(CB): b - c, 距离和为 b -a,

所以C点具体在哪不影响结果

```java
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**

思路: 证明为什么Median到各点的距离最短 <https://discuss.leetcode.com/topic/71068/3-line-c-solution-with-rigorous-math-proof-same-as-problem-best-meeting-point>

```java
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：**&#x65F6;间复杂度O(nlogn), 空间复杂度O(1)

**Quick Select to Get Median:** 时间复杂度O(n), 空间复杂度O(logn), 因为quickSelect用了递归