首页 > itarticle > [leetcode] problem 462 – minimum moves to equal array elements ii

[leetcode] problem 462 – minimum moves to equal array elements ii

admin 11月 13, 2020 0

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]

Code

public int (int[] nums) {
    int result = 0;
    int n = nums.length;

    int median = quickSelect(nums, n / 2, 0, n - 1);

    for (int num : nums)
        result += Math.abs(num - median);

    return result;
}

private int quickSelect(int[] nums, int k, int start, int end) {
    if (start == end)
        return nums[start];

    int i = partition(nums, start, end);

    if (i == k)
        return nums[k];
    else if (i > k)
        return quickSelect(nums, k, start, i - 1);
    else
        return quickSelect(nums, k, i + 1, end);
}

private int partition(int[] nums, int left, int right) {
    int pivot = left;

    while (left < right) {
        while (left < right && nums[left] < nums[pivot])
            left++;

        while (left < right && nums[right] >= nums[pivot])
            right--;

        swap(nums, left, right);
    }

    swap(nums, left, pivot);
    return left;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}