215. Kth Largest Element in an Array (2)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution

QuickSelect

根據lastPrivotIndex，決定要往哪邊進行sort，若lastPrivotIndex > k，代表 k在 lastPrivotIndex左邊，所以sort左半，反之sort 右半

TimeComplexity: O(n)

Discard half each time: n+(n/2)+(n/4)..1 = n + (n-1) = O(2n-1) = O(n), because n/2+n/4+n/8+..1=n-1.

    public int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        return quickSelect(nums, 0, nums.length-1,  k-1);
    }
    
    public void shuffle(int[] nums){
        for(int i = 0 ; i < nums.length; i++){
            swap(nums, i, (int)(Math.random()*(nums.length-1)));
        }
    }
    
    public int quickSelect(int[] nums, int start, int end, int k){
        int lastPrivotIndex = start;
        int pivot = nums[end];
        for(int i = start; i < end; i++){
            if(pivot < nums[i]){
                swap(nums, lastPrivotIndex, i);
                lastPrivotIndex++;
            }
        }
        swap(nums, lastPrivotIndex, end);
        if(lastPrivotIndex== k){
            return pivot;
        }
        else if (lastPrivotIndex< k){
            //k is on the right ride
            return quickSelect(nums, lastPrivotIndex+1, end, k);
        }
        else {
            //k is on the left ride
            return quickSelect(nums, start, lastPrivotIndex-1, k);
        }
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }