更新時間：2025-04-04

• 算法題解目錄匯總：算法刷題記錄——題解目錄匯總
• 技術博客總目錄：計算機技術系列博客——目錄頁

優先整理熱門100及面試150，不定期持續更新，歡迎關注！

---

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

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設計并實現時間復雜度為 O(n) 的算法解決此問題。

示例 1:

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

示例 2:

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

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

---

方法：三向切分快速選擇法

利用快速選擇算法結合三向切分，高效定位第K大元素。

1. 三向切分：

   • 將數組分為三個區域：大于基準值、等于基準值、小于基準值；
   • 采用類似荷蘭國旗問題的分區方式，一次遍歷完成分類；

2. 遞歸選擇：

   • 根據當前分區后的元素數量分布，決定遞歸處理方向；
   • 大于區域元素足夠時遞歸處理前部；
   • 數量不足但包含等于區域時直接返回基準值；
   • 否則遞歸處理后部并調整k值；

隨機選擇基準值避免最壞情況，每次遞歸至少排除一個區域元素。

代碼實現(Java)：

class Solution {public int findKthLargest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, k);}private int quickSelect(int[] nums, int left, int right, int k) {if (left == right) {return nums[left];}Random rand = new Random();int pivotIndex = left + rand.nextInt(right - left + 1);int pivot = nums[pivotIndex];// 三向切分（荷蘭國旗問題）int low = left;int high = right;int mid = left;while (mid <= high) {if (nums[mid] > pivot) {  // 大于pivot的交換到前部swap(nums, low, mid);low++;mid++;} else if (nums[mid] < pivot) { // 小于pivot的交換到后部swap(nums, mid, high);high--;} else {  // 等于時繼續后移mid++;}}// 計算各區域元素數量int gtCount = low - left;       // 大于pivot的數目int eqCount = high - low + 1;   // 等于pivot的數目if (k <= gtCount) {             // 目標在大于區域return quickSelect(nums, left, low - 1, k);} else if (k <= gtCount + eqCount) { // 目標在等于區域return pivot;} else {                        // 目標在小于區域return quickSelect(nums, high + 1, right, k - gtCount - eqCount);}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

復雜度分析

平均時間復雜度 O(n)，最壞情況 O(n^2)。

---

聲明

1. 本文版權歸 CSDN 用戶 Allen Wurlitzer 所有，遵循CC-BY-SA協議發布，轉載請注明出處。
2. 本文題目來源 力扣-LeetCode ，著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。