215. Kth Largest Element in an Array - Medium

前往題目

想法

• 只想得到用sort之後🤣

思路

1. 用Priority queue，默認是從小到大，所以超過k個數字的時候把top去掉就好，最後會剩下最小到第k大的元素

或是QuickSelect: 平均O(N)，但是最差情況是$O(N^2)$

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue();

        // Check all the numbers
        for (int num : nums) {
            // Add to the pq
            pq.offer(num);
            // Remove the top element
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // Return the top
        return pq.peek();
    }
}

2024/05/07

• 簡單