215 Kth Largest Element in an Array

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.

Credits:
Special thanks to@mithmattfor adding this problem and creating all test cases.

Solution)

Priority Queue

class Solution {
    public int findKthLargest(int[] nums, int k) {
        final PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int val : nums) {
            pq.offer(val);

            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
}

Quick Sort idea using k

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return Integer.MAX_VALUE;
        // find k-1th element (kth largest)
        return findKthLargest(nums, 0, nums.length - 1, k-1);
    }    

    public int findKthLargest(int[] nums, int start, int end, int k) {// quick select: kth largest
        if (start > end) return Integer.MAX_VALUE;

        int pivot = nums[end];// Take A[end] as the pivot, 
        int left = start;
        for (int i = start; i < end; i++) {
            if (nums[i] >= pivot) // Put numbers < pivot to pivot's left
                swap(nums, left++, i);            
        }
        swap(nums, left, end);// Finally, swap A[end] with A[left]

        if (left == k)// Found kth largest number
            return nums[left];
        else if (left < k)// Check right part
            return findKthLargest(nums, left + 1, end, k);
        else // Check left part
            return findKthLargest(nums, start, left - 1, k);
    } 

    void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;                
    }
}