在算法面試中，查找數組中第K個最大元素是一個經典問題。LeetCode第215題要求我們在未排序的數組中找到第K大的元素。本文將介紹兩種高效的解決方案：快速選擇算法和堆（優先隊列）方法，幫助你全面掌握這道高頻面試題。

問題描述

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。

請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例 1：

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

示例 2：

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

注意： 可以假設 k 總是有效的，即 1 ≤ k ≤ nums.length。

解法一：快速選擇算法（QuickSelect）

算法思想

快速選擇算法基于快速排序的分區思想，通過每次分區將數組分為兩部分，然后根據目標位置選擇繼續分區其中一側，從而在平均 O(n) 的時間復雜度內解決問題。

算法步驟

1. 隨機選擇樞軸：為了避免最壞情況，隨機選擇一個元素作為樞軸
2. 分區操作：
   • 將大于樞軸的元素移到左側
   • 將小于等于樞軸的元素移到右側
3. 比較樞軸位置：
   • 如果樞軸位置正好是k-1，返回該元素
   • 如果位置大于k-1，在左半部分繼續查找
   • 如果位置小于k-1，在右半部分繼續查找

Java實現

import java.util.Random;class Solution {public int findKthLargest(int[] nums, int k) {int left = 0;int right = nums.length - 1;int targetIndex = k - 1; // 第k大元素在降序數組中的索引Random rand = new Random();while (left <= right) {// 隨機選擇樞軸并交換到末尾int pivotIndex = left + rand.nextInt(right - left + 1);swap(nums, pivotIndex, right);// 分區操作，返回樞軸最終位置int partitionIndex = partition(nums, left, right);if (partitionIndex == targetIndex) {return nums[partitionIndex];} else if (partitionIndex > targetIndex) {right = partitionIndex - 1;} else {left = partitionIndex + 1;}}return -1; // 理論上不會執行到這里}// 分區函數：將大于樞軸的元素移到左側private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left;for (int j = left; j < right; j++) {if (nums[j] > pivot) {swap(nums, i, j);i++;}}swap(nums, i, right);return i;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

復雜度分析

• 時間復雜度：
  • 平均情況：O(n)
  • 最壞情況：O(n2)（但隨機樞軸有效避免最壞情況）
• 空間復雜度：O(1)

算法特點

1. 原地操作，不需要額外空間
2. 平均性能優異
3. 會修改原始數組

解法二：最小堆（優先隊列）

算法思想

使用最小堆維護數組中最大的k個元素。堆頂元素（最小值）即為第k大的元素。

算法步驟

1. 初始化大小為k的最小堆
2. 遍歷數組：
   • 當堆大小小于k時，直接添加元素
   • 當堆已滿且當前元素大于堆頂時，替換堆頂元素
3. 遍歷結束后，堆頂元素即為結果

Java實現

import java.util.PriorityQueue;class Solution {public int findKthLargest(int[] nums, int k) {// 創建最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int num : nums) {if (minHeap.size() < k) {minHeap.offer(num);} else if (num > minHeap.peek()) {minHeap.poll();minHeap.offer(num);}}return minHeap.peek();}
}

復雜度分析

• 時間復雜度：O(n log k)
• 空間復雜度：O(k)

算法特點

1. 不修改原始數組
2. 適合處理流式數據
3. 代碼簡潔易懂
4. 時間復雜度穩定

兩種解法比較

特性	快速選擇算法	最小堆方法
時間復雜度	平均 O(n)，最壞 O(n2)	O(n log k)
空間復雜度	O(1)	O(k)
是否修改數組	是	否
適用場景	空間要求高，可修改數組	流式數據，保持原數組不變
穩定性	不穩定	穩定

測試示例

public class Main {public static void main(String[] args) {Solution solution = new Solution();int[] nums1 = {3, 2, 1, 5, 6, 4};int k1 = 2;System.out.println("示例1: " + solution.findKthLargest(nums1, k1)); // 5int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};int k2 = 4;System.out.println("示例2: " + solution.findKthLargest(nums2, k2)); // 4int[] nums3 = {7, 6, 5, 4, 3, 2, 1};int k3 = 3;System.out.println("示例3: " + solution.findKthLargest(nums3, k3)); // 5}
}

總結

LeetCode 215題"數組中的第K個最大元素"有兩種高效解法：

1. 快速選擇算法：

   • 優點：平均時間復雜度O(n)，空間復雜度O(1)
   • 缺點：最壞情況O(n2)，修改原數組
   • 適用場景：空間要求高，可接受修改數組

2. 最小堆方法：

   • 優點：時間復雜度穩定O(n log k)，不修改原數組
   • 缺點：空間復雜度O(k)
   • 適用場景：流式數據，需要保持原數組不變

根據具體問題場景選擇合適的解法：

• 對于內存敏感的場景，優先選擇快速選擇算法
• 對于需要保持原數組或處理流式數據的場景，選擇最小堆方法

掌握這兩種解法及其適用場景，可以幫助你在面試中靈活應對不同變種問題。