Kth Largest Element in an Array

題目描述

給定一個整數陣列 nums 和整數 k，回傳陣列中第 k 大的元素。注意是排序後的第 k 大，不是第 k 個不重複元素。

輸入: nums = [3,2,1,5,6,4], k = 2
輸出: 5

輸入: nums = [3,2,3,1,2,4,5,5,6], k = 4
輸出: 4

解題思路

建立大小 K 的 Min Heap

先放入前 K 個元素

遍歷剩餘元素

每個元素和堆頂比較

比堆頂大就替換

移除堆頂，加入新元素

堆頂就是答案

遍歷完成後，堆頂就是第 K 大

程式碼

C#

csharp

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        // C# PriorityQueue 是 Min Heap
        var minHeap = new PriorityQueue<int, int>();
 
        foreach (int num in nums) {
            minHeap.Enqueue(num, num);
            if (minHeap.Count > k) {
                minHeap.Dequeue(); // 移除最小的
            }
        }
        return minHeap.Peek(); // 堆頂 = 第 K 大
    }
}

TypeScript

typescript

function findKthLargest(nums: number[], k: number): number {
    // TypeScript 沒有內建 Heap，用排序模擬
    // 實際面試中可能要手寫 Heap 或用 QuickSelect
    const minHeap: number[] = [];
 
    for (const num of nums) {
        minHeap.push(num);
        minHeap.sort((a, b) => a - b); // 模擬 min heap
        if (minHeap.length > k) {
            minHeap.shift(); // 移除最小的
        }
    }
    return minHeap[0];
}
 
// 更高效的 QuickSelect 解法
function findKthLargestQuickSelect(nums: number[], k: number): number {
    const target = nums.length - k;
 
    function quickSelect(left: number, right: number): number {
        const pivot = nums[right];
        let p = left;
        for (let i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                [nums[i], nums[p]] = [nums[p], nums[i]];
                p++;
            }
        }
        [nums[p], nums[right]] = [nums[right], nums[p]];
 
        if (p === target) return nums[p];
        if (p < target) return quickSelect(p + 1, right);
        return quickSelect(left, p - 1);
    }
 
    return quickSelect(0, nums.length - 1);
}

Python

python

import heapq
 
def findKthLargest(nums: list[int], k: int) -> int:
    # Python heapq 是 min heap
    min_heap = []
 
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # 移除最小的
 
    return min_heap[0]  # 堆頂 = 第 K 大
 
# 更高效：直接用 nlargest
def findKthLargestPythonic(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

複雜度分析

| | Time | Space | |--|------|-------| | Min Heap | O(n log k) | O(k) | | QuickSelect | O(n) 平均, O(n²) 最壞 | O(1) | | 排序 | O(n log n) | O(1) |

圖解

[3,2,1,5,6,4] k=2

前 2 個→

Heap: [2,3]

→

加入 5 → [3,5] (移除 2)

→

加入 6 → [5,6] (移除 3)

→

加入 4 → [5,6] (4<5 不替換)

→

堆頂 5 = 第 2 大

進階觀點

💡面試追問

三種方法比較：排序 O(n log n)、Min Heap O(n log k)、QuickSelect O(n) 平均。面試官通常期望你知道三種方法並能分析取捨。

QuickSelect：基於快速排序的分割思想，平均 O(n) 但最壞 O(n^2)。可以用隨機 pivot 優化。面試高頻追問。

變體題：LC 347 Top K Frequent Elements（用 Heap 找前 K 高頻）、LC 973 K Closest Points to Origin。

理解測驗

🤔 為什麼用 Min Heap 而不是 Max Heap？

🤔 QuickSelect 的平均時間複雜度為什麼是 O(n)？