題目

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

一、代碼實現（快速選擇算法）

import ("math/rand""time"
)func findKthLargest(nums []int, k int) int {rand.Seed(time.Now().UnixNano())return quickSelect(nums, 0, len(nums)-1, k)
}func quickSelect(nums []int, left, right, k int) int {if left == right {return nums[left]}pivotIndex := rand.Intn(right-left+1) + leftpivotVal := nums[pivotIndex]// 三路分區low, mid, high := left, left, rightfor mid <= high {if nums[mid] > pivotVal {nums[low], nums[mid] = nums[mid], nums[low]low++mid++} else if nums[mid] == pivotVal {mid++} else {nums[mid], nums[high] = nums[high], nums[mid]high--}}leftLength := low - leftif k <= leftLength {return quickSelect(nums, left, low-1, k)}midLength := high - low + 1if k <= leftLength+midLength {return pivotVal}return quickSelect(nums, high+1, right, k-(leftLength+midLength))
}

二、算法分析

1. 核心思路

• 快速選擇算法：基于快速排序的分治思想，但每次僅遞歸處理包含目標的子數組。
• 三路分區：將數組劃分為大于、等于、小于基準值的三部分，減少不必要的遞歸。
• 隨機基準：隨機選擇基準值避免最壞情況，確保平均時間復雜度為O(n)。

2. 關鍵步驟

1. 隨機基準選擇：隨機選取一個元素作為基準值pivotVal。
2. 三路分區操作：
   • low指針左側元素均大于pivotVal。
   • mid遍歷數組，將元素分類到對應區域。
   • high指針右側元素均小于pivotVal。
3. 遞歸決策：
   • 若左區長度≥k，遞歸處理左區。
   • 若k在左區和中區總長內，直接返回pivotVal。
   • 否則遞歸處理右區，調整k值。

3. 復雜度

指標	值	說明
時間復雜度	O(n)	平均情況，每次處理規模減半
空間復雜度	O(log n)	遞歸調用棧深度（最壞O(n)，隨機化避免）

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 全相同元素：如[3,3,3], k=2，直接返回3。
• k=1或k=n：處理最大或最小元素。
• 逆序/順序數組：隨機基準確保效率。

2. 擴展應用

• 前k大元素：修改返回邏輯收集元素。
• 流式數據：結合堆結構處理動態數據。
• 多維數據：定義合適比較規則處理復雜結構。

3. 多語言實現

import randomdef findKthLargest(nums, k):def quick_select(left, right, k):if left == right:return nums[left]pivot_index = random.randint(left, right)pivot_val = nums[pivot_index]low, mid, high = left, left, rightwhile mid <= high:if nums[mid] > pivot_val:nums[low], nums[mid] = nums[mid], nums[low]low += 1mid += 1elif nums[mid] == pivot_val:mid += 1else:nums[mid], nums[high] = nums[high], nums[mid]high -= 1if k <= low - left:return quick_select(left, low-1, k)elif k <= (low - left) + (high - low +1):return pivot_valelse:return quick_select(high+1, right, k - (low - left + high - low +1))return quick_select(0, len(nums)-1, k)

import java.util.Random;public class Solution {private static final Random rand = new Random();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];int pivotIndex = rand.nextInt(right - left + 1) + left;int pivotVal = nums[pivotIndex];int low = left, mid = left, high = right;while (mid <= high) {if (nums[mid] > pivotVal) {swap(nums, low++, mid++);} else if (nums[mid] == pivotVal) {mid++;} else {swap(nums, mid, high--);}}int leftLen = low - left;if (k <= leftLen) return quickSelect(nums, left, low - 1, k);int midLen = high - low + 1;if (k <= leftLen + midLen) return pivotVal;return quickSelect(nums, high + 1, right, k - (leftLen + midLen));}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

五、總結與優化

1. 算法對比

方法	優勢	適用場景
快速選擇	平均O(n)	大規模數據求Top k
堆	適合動態數據	實時處理流數據
排序后取數	實現簡單	小規模數據

2. 工程優化

• 尾遞歸優化：減少遞歸棧深度。
• 迭代實現：改用循環結構避免棧溢出。
• 內存優化：處理原數組避免額外空間。

3. 擴展方向

• 并行處理：多線程加速分區過程。
• 適應性優化：根據數據分布自動選擇策略。
• 穩定性增強：處理元素相等時的穩定性需求。