LeetCode:Kth Largest Element in an Array

Kth Largest Element in an Array
Total Accepted: 59659 
Total Submissions: 175932 
Difficulty: Medium
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 @mithmatt for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
Hide Tags
 
Heap Divide and Conquer
Hide Similar Problems
 
(M) Wiggle Sort II (M) Top K Frequent Elements
考え方:
numsの最初のk要素を「大きなルート」スタックに構築し、その後[k+1,n]要素をスタックトップで比較します.スタックアイテムより大きい場合は、スタックを交換、再構築します.
時間複雑度=初回ヒープ時間+(n-k)ヒープ時間(すなわち最悪の場合は毎回交換、ヒープ)=logk+(n-k)logk=(n-k+1)logk
java code:

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for(int num : nums) {
            queue.offer(num);
            if(queue.size() > k) queue.poll();
        }
        return queue.peek();
    }
}