LeetCode 215.Kth Largest Element in an Array

Question

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.

For example, Given [3,2,1,5,6,4] and k = 2, return 5.

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

Explanation

常考题。可以有三种方法：a. 直接sort，然后找到第k个。b.用一个heap来存，这种方法遇到最大top kth 也可以做，或者遇到不停更新的数组，需要不停add的情况时，可以用这个来存。会很有效率。c.用quick sort来找partition aray来找。

这三种方法都写在下面了，包括时间空间效率分析。

Code

public class Solution {
    // public int findKthLargest(int[] nums, int k) {
    //     // O(NlgN) time + O(1) memory, but it would be very costing if you keep adding new elements. It's not efficiency to sort it all the time.
    //     int n = nums.length;
    //     Arrays.sort(nums);
    //     return nums[n-k];
    // }

    // public int findKthLargest(int[] nums, int k) {
    //     // O(NlogK) time + O(k) memory
    //     PriorityQueue<Integer> p = new PriorityQueue<Integer>();
    //     for (int i=0; i<nums.length; i++) {
    //         p.add(nums[i]);
    //         if (p.size() > k) p.poll();
    //     }
    //     return p.poll();

    // }


    public int findKthLargest(int[] nums, int k) {
        // O(N) running time + O(1) memeory Quick sort
        return quickSelect(nums, k-1, 0, nums.length-1);
    }

    private int quickSelect(int[] nums, int k, int left, int right) {
        int pivot = nums[(left+right)/2];
        int orgl = left, orgr = right;
        while(left <= right) {
            while(nums[left] > pivot) {
                left ++;
            }
            while(nums[right] < pivot) {
                right --;
            }
            if (left <= right) {
                swap(nums, right, left);
                left ++;
                right --;
            }
        }
        if(orgl < right && k <= right) return quickSelect(nums,k, orgl, right);
        if(left < orgr && k >= left) return quickSelect(nums, k,left, orgr);
        return nums[k];
    }
    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1] ;
        nums[index1] =  nums[index2];
        nums[index2] =tmp;
    }




}