462. Minimum Moves to Equal Array Elements II

二刷 08/2022

Version #1 Quick Select

Time O(N)

Space O(1)

Runtime: 4 ms, faster than 91.61% of Java online submissions for Minimum Moves to Equal Array Elements II.

Memory Usage: 46.6 MB, less than 11.84% of Java online submissions for Minimum Moves to Equal Array Elements II.

class Solution {

    public int minMoves2(int[] nums) {

        // find the k/2 the number in the array

        // 0  1  2  3

        int target = nums.length / 2;

        int start = 0, end = nums.length - 1;

        Random rd = new Random();

        int k = nums.length;

        while (start <= end) {

            k = partition(nums, start, end, rd);

            if (k == target) {

                break;

            }

            if (k < target) {

                start = k + 1;

            } else {

                end = k - 1;

            }

        }

        int sum = 0;

        for (int num : nums) {

            sum += Math.abs(num - nums[k]);

        }

        return sum;

    }

    

    private int partition(int[] nums, int start, int end, Random rd) {

        int pivot = start + rd.nextInt(end - start + 1);

        swap(nums, start, pivot);

        int left = start + 1, right = end;

        while (left <= right) {

            while (left <= right && nums[left] < nums[start]) {

                left++;

            }

            while (left <= right && nums[right] > nums[start]) {

                right--;

            }

            if (left <= right) {

                swap(nums, left, right);

                left++;

                right--;

            }

        }

        // all numbers less than or equals to nums[start] are on the left side of left

        //   right, x, left

        //   right, left

        

        swap(nums, start, right);

        return right;

    }

    

    private void swap(int[] nums, int a, int b) {

        int temp = nums[a];

        nums[a] = nums[b];

        nums[b] = temp;

    }

} 

一刷 07/2022

Version #1 Quick Select

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 99.89% of Java online submissions for Minimum Moves to Equal Array Elements II.

Memory Usage: 43.1 MB, less than 87.99% of Java online submissions for Minimum Moves to Equal Array Elements II.

class Solution {

    public int minMoves2(int[] nums) {

        int median = findKth(nums, nums.length / 2);

        int sum = 0;

        for (int num : nums) {

            sum += Math.abs(num - median);

        }

        return sum;

    }

    

    private int findKth(int[] nums, int k) {

        int index = nums.length;

        int start = 0, end = index - 1;

        Random rd = new Random();

        // System.out.printf("k=%d\n", k);

        while (index != k) {

            index = partition(nums, start, end, rd);

            // System.out.printf("index=%d\n", index);

            if (index == k) {

                return nums[index];

            }

            if (index < k) {

                start = index + 1;

            } else {

                end = index - 1;

            }

        }

        return nums[index];

    }

    

    private int partition(int[] nums, int start, int end, Random rd) {

        int pivot = start + rd.nextInt(end - start + 1);

        swap(nums, start, pivot);

        int left = start + 1, right = end;

        while (left <= right) {

            while (left <= right && nums[left] < nums[start]) {

                left++;

            }

            while (left <= right && nums[right] > nums[start]) {

                right--;

            }

            if (left <= right) {

                swap(nums, left, right);

                left++;

                right--;

            }

            // right _ left or right left

        }

        swap(nums, start, right);

        return right;

    }

    

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}