Kth Largest Element in an Array

LC 215 題意

• (Heap / Quickselect)
• 給定一個整數陣列 nums 和一個整數 k，請回傳陣列中第 k 大的元素（不是第 k 個不同元素）。
• Ex.
  Input: nums = [3,2,1,5,6,4], k = 2
  Output: 5

thoughts

• Min-Heap 解法 (O(n log k))
  • 使用最小堆，維持大小為 k 的 heap。
  • 當 heap 大於 k 時，移除最小值。
  • 最後堆頂即為第 k 大的數。
• Quickselect 解法 (O(n))
  • 改良版快速排序（只 partition 一邊）。

kotlin（Heap）

import java.util.PriorityQueue

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>()
        for (num in nums) {
            pq.offer(num)
            if (pq.size > k) pq.poll()
        }
        return pq.peek()
    }
}

Follow-up

• 如何在 O(n) 時間找到第 k 大？（→ Quickselect）
• 若資料流持續輸入，如何動態維護第 k 大？（→ 使用 Min-Heap Stream）
• 若要找第 k 小的元素呢？（→ 改用 Max-Heap）