462 Minimum Moves to Equal Array Elements II

Search…

462. Minimum Moves to Equal Array Elements II​
1. Question
Given anon-emptyinteger 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:
1
Input: [1,2,3]
2
​
3
Output: 2
4
​
5
Explanation:
6
​
7
Only two moves are needed (remember each move increments or decrements one element):
8
[1,2,3] => [2,2,3] => [2,2,2]
Copied!
2. Implementation
(1) Sort + Two Pointers
思路: 给定两个点A和B, 如果要在它们之间找到一个点C，算出AC和CB的距离，可知Dist(AC): c - a, Dist(CB): b - c, 距离和为 b -a,
所以C点具体在哪不影响结果
1
class Solution {
2
    public int minMoves2(int[] nums) {
3
        Arrays.sort(nums);
4
​
5
        int start = 0, end = nums.length - 1;
6
        int moves = 0;
7
​
8
        while (start < end) {
9
            moves += nums[end] - nums[start];
10
            ++start;
11
            --end;
12
        }
13
        return moves;
14
    }
15
}
Copied!
(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​
1
class Solution {
2
    public int minMoves2(int[] nums) {
3
        int n = nums.length;
4
        int median = quickSelect(nums, 0, n - 1, n/2);
5
        int moves = 0;
6
​
7
        for (int num : nums) {
8
            moves += Math.abs(num - median);
9
        }
10
        return moves;
11
    }
12
​
13
    public int quickSelect(int[] nums, int start, int end, int k) {
14
        int pivot = partition(nums, start, end);
15
​
16
        if (pivot < k) {
17
            return quickSelect(nums, pivot + 1, end, k);
18
        }
19
        else if (pivot > k) {
20
            return quickSelect(nums, start, pivot - 1, k);
21
        }
22
        else {
23
            return nums[pivot];
24
        }
25
    }
26
​
27
    public int partition(int[] nums, int start, int end) {
28
        int mid = start + (end - start) / 2;
29
        swap(nums, mid, end);
30
​
31
        for (int i = start; i < end; i++) {
32
            if (nums[i] < nums[end]) {
33
                swap(nums, i, start);
34
                ++start;
35
            }
36
        }
37
​
38
        swap(nums, start, end);
39
        return start;
40
    }
41
​
42
    public void swap(int[] nums, int i, int j) {
43
        int temp = nums[i];
44
        nums[i] = nums[j];
45
        nums[j] = temp;
46
    }
47
}
Copied!
3. Time & Space Complexity
Sort + Two Pointers：时间复杂度O(nlogn), 空间复杂度O(1)
Quick Select to Get Median: 时间复杂度O(n), 空间复杂度O(logn), 因为quickSelect用了递归

406 Queue Reconstruction by Height

493 Reverse Pairs

Last modified 2yr ago

Copy link

Contents

462. Minimum Moves to Equal Array Elements II

1. Question

2. Implementation

3. Time & Space Complexity

462. Minimum Moves to Equal Array Elements II​

1. Question

2. Implementation

3. Time & Space Complexity

462. Minimum Moves to Equal Array Elements II