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.

// Time: O(nlogn), Space: O(k)
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else {
                if (num > pq.peek()) {
                    pq.poll();
                    pq.offer(num);
                }
            }
        }
        return pq.peek();
    }
}
// Time: O(nlogn), Space: O(1)
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || k > nums.length) return 0;
        return helper(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int helper(int[] nums, int start, int end, int k) {
        int left = start;
        int right = end;
        int pivot = nums[end];
        while (left < right) {
            while (left < right && nums[left] < pivot) left++;
            while (left < right && nums[right] >= pivot) right--;
            if (left == right) break;
            swap(nums, left, right);
        }
        swap(nums, left, end);
        if (left == k) return pivot;
        else if (left < k) return helper(nums, left + 1, end, k);
        else return helper(nums, start, left - 1, k);
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
Advertisements