1、題目描述

給定整數數組?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

---

2、代碼實現

會超時的代碼

class Solution
{
public:int findKthLargest(vector<int>& nums, int k){int target = k - 1;int left = 0, right = nums.size() - 1;while (left <= right) {int pos = partition(nums, left, right);if (pos == target) {return nums[pos];}else if (pos < target) {left = pos + 1;}else {right = pos - 1;}}return -1;}int partition(vector<int>& nums, int left, int right){static bool initSrand = false;if (!initSrand) {srand(time(0));}int pivot_index = left + (rand() % (right - left + 1));int pivot = nums[pivot_index];swap(nums[right], nums[pivot_index]);int i = left - 1;int j;for (j = left; j < right; j++) {if (nums[j] > pivot) {swap(nums[j], nums[++i]);}}swap(nums[++i], nums[right]);return i;}
};

正確的代碼

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <tuple>
#include <vector>using namespace std;class Solution {
public:/*** @brief 在未排序數組中找到第k大的元素（基于三向切分的快速選擇算法）* @param nums 待搜索的整數數組* @param k 目標元素的排序位置（第k大）* @return 第k大的元素值* * @note 時間復雜度：平均O(n)，最壞O(n2)（但概率極低）* @note 空間復雜度：O(1) 原地操作*/int findKthLargest(vector<int>& nums, int k) {int left = 0, right = nums.size() - 1;  // 當前搜索范圍while (true) {// 隨機選擇基準值避免最壞情況int pivot_idx = left + rand() % (right - left + 1);int pivot = nums[pivot_idx];// 三向切分數組（大于區｜等于區｜小于區）auto [greater_end, less_start] = threeWayPartition(nums, left, right, pivot);// 計算各區域元素數量int greater_cnt = greater_end - left;      // 大于區的元素數量int equal_cnt = less_start - greater_end + 1; // 等于區的元素數量/* 決策樹 */if (k <= greater_cnt) {          // 目標在大于區right = greater_end - 1;    // 縮小搜索范圍到左區} else if (k <= greater_cnt + equal_cnt) { // 命中等于區return pivot;               // 直接返回結果} else {                        // 目標在小于區k -= (greater_cnt + equal_cnt); // 調整k的相對位置left = less_start + 1;      // 縮小搜索范圍到右區}}}private:/*** @brief 三向切分數組* @param nums 待切分數組* @param left 當前處理區間的左邊界* @param right 當前處理區間的右邊界* @param pivot 基準值* @return tuple<int, int> 返回兩個邊界位置：*         - greater_end: 大于區的結束位置（最后一個大于元素的下一位置）*         - less_start: 小于區的開始位置（第一個小于元素的前一位置）* * @note 切分結果：*        [left, greater_end)    > pivot*        [greater_end, less_start] == pivot*        (less_start, right]    < pivot*/tuple<int, int> threeWayPartition(vector<int>& nums, int left, int right, int pivot)                 {int greater_end = left;   // 大于區的右邊界（左側元素均>pivot）int less_start = right;   // 小于區的左邊界（右側元素均<pivot）int i = left;             // 當前掃描指針while (i <= less_start) { // 掃描未處理區域if (nums[i] > pivot) {// 將大元素交換到大于區末尾swap(nums[i++], nums[greater_end++]);} else if (nums[i] == pivot) {// 等于元素直接跳過++i;} else {// 將小元素交換到小于區頭部（注意i不遞增）swap(nums[i], nums[less_start--]);}}return {greater_end, less_start};}
};

3、解題思路

這道題的難度很高，我最開始是采用普通的快速選擇，雖然答案是對的，但是會超時，所以我們該用三向切分策略，也就是將數組分為[left, greater_end)、[greater_end, less_start]、(less_start, right] 三個區間，不過需要注意一下開閉區間。

核心思想

1. ?隨機化基準值
   每次隨機選擇基準值 (pivot)，有效避免輸入數據有序導致的 O(n2) 最壞時間復雜度。

2. ?三向切分 (3-Way Partition)
   將數組劃分為三個區域：

   • ?大于區：所有元素 > pivot
   • ?等于區：所有元素 == pivot
   • ?小于區：所有元素 < pivot

3. ?遞歸決策
   根據各區域元素數量與k值的關系，決定后續搜索方向：

   • 若k在 ?大于區：縮小范圍到左區間
   • 若k在 ?等于區：直接返回pivot
   • 若k在 ?小于區：調整k值后搜索右區間

執行流程

1. ?初始化搜索范圍
   初始處理整個數組 (left=0, right=n-1)

2. ?隨機選擇基準值
   在?[left, right]?區間隨機選取一個元素作為基準值，確保算法魯棒性

3. ?三向切分操作

   • 使用三個指針：
     • greater_end：標記大于區的右邊界
     • less_start：標記小于區的左邊界
     • i：當前掃描指針
   • 掃描過程：
     • 大元素 → 交換到大于區末尾，指針右移
     • 等于元素 → 跳過
     • 小元素 → 交換到小于區頭部，指針不動（需重新檢查）
4. 決策邏輯

if (k <= greater_cnt) { ? ? ? ? ?// 目標在左區
? ? right = greater_end - 1; ? ?
} else if (k <= greater_cnt + equal_cnt) { // 命中等于區
? ? return pivot; ? ? ? ? ? ? ??
} else { ? ? ? ? ? ? ? ? ? ? ? ?// 目標在右區
? ? k -= (greater_cnt + equal_cnt);?
? ? left = less_start + 1; ? ? ?
}

常見疑問解答

1. ?為什么用隨機pivot？

   • 避免最壞時間復雜度，保證算法平均性能

2. ?less_start指針為何不遞增i？

   • 交換后的元素來自未處理區域，需重新判斷其值

3. ?如何處理重復元素？

   • 三向分區將相同元素集中在中間區域，減少無效比較