第 k 大問題

問題描述

給定一個未經排序的數組和一個整數 k，要求找到這個數組中第 k 大的元素。例如，當輸入數組為[3, 2, 1, 5, 6, 4]且 k 為 2 時，算法應該返回數值 5 ，因為 5 是這個數組中的第二大元素。

解題思路

一種比較直觀的解決方案是首先將數組排序，然後直接返回排序後數組的第 k 個元素。不過，這種做法需要 $O(n logn)$ 的時間複雜度，對於大規模數據來說效率就會較低。

我們可以採用一種更有效的解決方案：利用二分搜索的思想。

1. 用一個陣列a紀錄每個數字出現的次數。假設輸入x，a[x]就加一( 前提是x不能太大 )，並用一個陣列pre紀錄a的前綴和。
2. pre有單調性，對pre二分搜找到第一個大於等於n - k + 1的那個 index。
3. 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