C++60分TLE，求助

Chase12345 @ 2023-09-08 08:44:11

#include <bits/stdc++.h>
using namespace std;

int a[5000000];
map <int, int> check;

int findKth (int a[], int len, int key) {
    for (int i = 0; i < len; i++)
        check[a[i]]++;
    int index = 0;
    for (auto p : check) {
        for (int i = 1; i <= p.second; i++) {
            if (index == key)
                return p.first;
            a[index++] = p.first;
        }
    }
}

int main() {
    int n, key;
    cin >> n >> key;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << findKth (a, n, key) << endl;
    return 0;
}

by Chase12345 @ 2023-09-08 09:02:33

我知道时间复杂度是O(nlogn)，但是不知道怎么优化……

by wannacry_ @ 2023-09-08 09:35:58

你这个相当于是桶排，时间最坏复杂度是 O(n^2)

by Chase12345 @ 2023-09-08 09:53:40

@wannacry_ 好像算过了，是O(nlogn)

by One_JuRuo @ 2023-09-08 09:57:46

@Chase12345 是nlogn，试试cin改scanf？

by Chase12345 @ 2023-09-08 10:00:20

不行，还是TLE

by One_JuRuo @ 2023-09-08 10:03:33

@Chase12345 那就别用 STL，常数大，就用分治呗

by Chase12345 @ 2023-09-08 10:04:43

@One_JuRuo 好吧，用nth_elementAC了

by Chase12345 @ 2023-09-08 10:05:21

@One_JuRuo 分治也可以了

by wannacry_ @ 2023-09-08 10:10:36

@One_JuRuo %%%

by One_JuRuo @ 2023-09-08 10:11:02

@wannacry_ 什么都 % 只会害了你