問題描述#
給定一個未經排序的數組和一個整數 k，要求找到這個數組中第 k 大的元素。例如，當輸入數組為[3, 2, 1, 5, 6, 4]且 k 為 2 時，算法應該返回數值 5 ，因為 5 是這個數組中的第二大元素。
解題思路#
一種比較直觀的解決方案是首先將數組排序，然後直接返回排序後數組的第 k 個元素。不過，這種做法需要 \(O(n logn)\) 的時間複雜度，對於大規模數據來說效率就會較低。
我們可以採用一種更有效的解決方案：利用二分搜索的思想。
- 用一個陣列
a紀錄每個數字出現的次數。假設輸入x，a[x]就加一( 前提是x不能太大 )，並用一個陣列pre紀錄a的前綴和。 pre有單調性，對pre二分搜找到第一個大於等於n - k + 1的那個index。index就是我們要找的值
這種解法的時間複雜度為 \(O(n)\)，其中n是數組長度。
#include <bits/stdc++.h>
using namespace std;
int num[100], n, k;
int a[100], pre[100], mx = 0;
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> num[i];
mx = max(mx, num[i]);
a[num[i]]++;
}
for (int i = 1; i <= mx; i++) {
pre[i] = pre[i - 1] + a[i];
}
int l = 0, r = mx + 1, tar = n - k + 1;
int idx = lower_bound(pre, pre + n, tar) - pre;
cout << idx << '\n';
}
假設輸入為：
9 3
2 4 3 9 5 8 1 2 5
輸出為：
5
