Java randomized Quick Select solution, O(n) time.


  • 0

    Note: The performance varies because of the random pivot selection.

    public int minMoves2(int[] nums) {
        int n = nums.length;
        int moves = 0;
        int medianPos = n/2;
        int med = findKthSmallest(nums, medianPos, 0, n - 1);
        for (int i = 0; i < nums.length; i++) {
            moves += Math.abs(nums[i] - med);
        }
        return moves;
    }
    private int findKthSmallest(int [] nums, int k, int start, int end) {
        if (start == end) return nums[start];
        // Random pivot
        Random rand = new Random();
        int indexSwitch = rand.nextInt(end - start) + start;
        swap(nums, end, indexSwitch);
        // If you remove the 3 lines above, the code still works.
        int pivot = nums[end];
        int i = start;
        int j = end - 1;
        while (i < j) {
            if (nums[i] < pivot) {
                i++;
                continue;
            }
            if (nums[j] >= pivot) {
                j--;
                continue;
            }
            swap(nums, i, j);
        }
        int pos = 0;
        if (nums[j] >= pivot) {
            swap(nums, j, end);
            pos = j;
        }
        else {
            swap(nums, j+1, end);
            pos = j+1;
        }
        if (pos == k) return nums[pos];
        else if (pos < k) return findKthSmallest(nums, k, pos + 1, end);
        else return findKthSmallest(nums, k, start, pos - 1);
    }
    private void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.