LeetCode 215 數組中的第 K 個最大元素：排序、堆、快選三種解法對比

LeetCode 215 數組中的第 K 個最大元素

題目描述

在未排序數組中找到第 k 個最大 元素。注意是排序後的第 k 位，而非第 k 個不重複元素。

• 示例：[3,2,1,5,6,4], k=2 → 返回 5
• 約束：1 ≤ k ≤ 數組長度

三種核心解法對比

解法一：全量排序（最簡潔）

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums); // 升序
    return nums[nums.length - k];
}

解法二：最小堆（流式/大數據友好）

public int findKthLargest(int[] nums, int k) {
    // 小頂堆，堆頂最小
    PriorityQueue minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小，保持堆大小 = k
        }
    }
    return minHeap.peek(); // 堆頂即第 k 大
}

解法三：快速選擇（原地 Partition）

public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k; // 第 k 大 = 升序索引 target
    int left = 0, right = nums.length - 1;
    while (true) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == target) return nums[pivotIndex];
        else if (pivotIndex < target) left = pivotIndex + 1;
        else right = pivotIndex - 1;
    }
}

private int partition(int[] nums, int left, int right) {
    // 隨機選擇 pivot 避免最壞 O(n²)
    int random = left + new Random().nextInt(right - left + 1);
    swap(nums, random, right);
    int pivot = nums[right];
    
    int storeIndex = left;
    for (int i = left; i < right; i++) {
        if (nums[i] < pivot) {
            swap(nums, storeIndex++, i);
        }
    }
    swap(nums, storeIndex, right);
    return storeIndex;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}

關鍵點總結

1. 索引轉換：第 k 大 ⇔ 升序索引 n - k
2. 堆大小固定 k：插入後超過 k 即彈出，保證堆內始終是前 k 大
3. 隨機化 Partition：防止有序/近有序數組退化到 O(n²)
4. Java API 選擇：PriorityQueue 默認最小堆，無需自定義比較器

擴展變體

• 第 k 小：Arrays.sort(nums); return nums[k-1]; 或 最大堆
• 數據流中位數：雙堆（大頂堆存小半、小頂堆存大半）
• Top K 問題：堆法通用，空間 O(k) 極具優勢