數組中的第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$

解法1（堆維護前k大元素）

時間復雜度$O（nlogk）$ 空間復雜度$O（k)$

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> pq; for(auto& num: nums){pq.emplace(num);if(pq.size() > k){pq.pop();   // 堆中元素超過k個，彈出最小的那個}}return pq.top();   }
};

解法2 手寫堆維護

思路：

• $nums$種存放二叉堆，索引$[0,n?1]$對應按層序遍歷對應的元素，對于下標從0開始的某節點$i$,左右孩子節點編號分別為$i?2+1,i?2+2$
• 下沉操作：$maxHeapify$操作為將二叉堆數組$nums$索引$i$處元素下沉
• 建堆操作：我們從最后一個非葉子節點$heapSize/2?1$開始倒序遍歷，從下往上下沉
• 刪除操作：每次將堆頂交換到數組末尾，再將$heapSize$減一，最后再調整新的堆頂即可
• 時間復雜度$O（nlogn）$ 空間復雜度$O（logn)$ 因為最大堆需要維護n個結點

class Solution {
public:// down void maxHeapify(vector<int>& a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest]) {largest = l;}if (r < heapSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a[i], a[largest]);maxHeapify(a, largest, heapSize);}}// initialize void buildMaxHeap(vector<int>& a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; i--) {maxHeapify(a, i, heapSize);}}int findKthLargest(vector<int>& nums, int k) {int heapSize = nums.size();buildMaxHeap(nums, heapSize); // 建堆// 執行k-1次提取最大值操作for (int i = nums.size() - 1; i >= nums.size() - k + 1; i--) {swap(nums[0], nums[i]);   // 調整堆頂-- heapSize;              // 刪除堆maxHeapify(nums, 0, heapSize); }return nums[0];}
};

解法3（快速選擇算法）

我們首先來回顧一下快排的實現

void quickSort(vector<int>& nums, int l, int r) {if (l >= r) return;// - i 初始在左邊界左側（l-1）// - j 初始在右邊界右側（r+1）// - 基準值 x 選中間元素（避免極端情況如全排序數組導致最壞時間復雜度）int i = l - 1, j = r + 1;int x = nums[(l + r) >> 1]; // 位運算代替 (l + r) / 2，等價且更高效// partition ：雙指針從兩端向中間移動while (i < j) {// 移動左指針 i：跳過所有小于 x 的元素，直到找到 >=x 的元素do i++; while (nums[i] < x); // 移動右指針 j：跳過所有大于 x 的元素，直到找到 <=x 的元素do j--; while (nums[j] > x);//  如果指針未交錯，交換左右指針的元素（確保左邊 <=x，右邊 >=x）if (i < j) swap(nums[i], nums[j]);}// 4. 遞歸排序左右子數組：quickSort(nums, l, j), quickSort(nums, j + 1, r);
}

• 快速選擇（$Quickselect$）算法是一種用于在未排序的列表中找到第k小（或第k大）元素的高效算法。與快速排序一樣，它使用分治策略，但不同于快速排序的是，它只遞歸處理包含目標元素的那一部分，而不是全部。這使得快速選擇的平均時間復雜度為$O(n)$，最壞情況為$O(n^2)$，但在實際應用中，通過隨機化選取樞軸（$pivot$）可以避免最壞情況。
• 復雜度：遞歸時，每層時間復雜度為$O(n)$,但并不是都進入左右兩部分遞歸。僅進入一側遞歸在平均情況下 數組長度會減半，故平均情況下的時間復雜度為 $n+n/2+n/4+\dots +1=O(n)$

以下是快速選擇實現找第K大元素的具體實現：

class Solution {
public:int quick_select(vector<int>& nums, int l, int r, int k) {if (l == r) return nums[k];int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 若選取nums[l], 極端樣例 時間會很久//int x = nums[rand() % (r - l + 1) + l], i = l - 1, j = r + 1; // 隨機選取while (i < j) {do i ++ ; while (nums[i] > x); // 注意是第k大 上面的模板是升序排序do j -- ; while (nums[j] < x);if (i < j) swap(nums[i], nums[j]);}if (k <= j) return quick_select(nums, l, j, k);else return quick_select(nums, j + 1, r, k);}int findKthLargest(vector<int>& nums, int k) {//srand(time(0)); // 隨機種子return quick_select(nums, 0, nums.size() - 1, k - 1); // 0-base}
};

例題：P1923 【深基9.例4】求第 k 小的數

#include <bits/stdc++.h>using namespace std;const int N = 5e6 + 7;int n, k;
int a[N];int quick_select(int nums[], int l, int r, int k) {if (l == r) return nums[k];int x = nums[l], i = l - 1, j = r + 1;while (i < j) {// paration 方向改一下即可do i ++; while (nums[i] < x); do j --; while (nums[j] > x);if (i < j) swap(nums[i], nums[j]);}if (k <= j) return quick_select(nums, l, j, k);else return quick_select(nums, j + 1, r, k);
}int main() {scanf("%d%d", &n, &k);//getchar();for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}printf("%d\n", quick_select(a, 0, n - 1, k));return 0;
}

參考

• LeetCode官方題解：數組中的第K個最大元素
• yxc常用代碼模板1——基礎算法
• LeetCode 215. 數組中的第K個最大元素