sort排序
这是最直接暴力的方法,时间复杂度为\(O(nlog_n)\)
直接排序,输出第k小的值即可
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i) cin >> a[i];
sort(a + 1, a + n + 1);
cout << a[k] << endl;
return 0;
}
快速选择算法
时间复杂度的计算主要关注左右两个指针的移动,总次数为\(n+\frac{n}{2}+\frac{n}{4} + ...\),所以时间复杂度为\(O(n)\)
具体内容请见快速排序引申出的快速选择算法
大根堆
因为需要遍历每个元素\(O(n)\),且每个元素插入堆中的复杂度为\(O(log_n)\),所以时间复杂度为\(O(nlog_n)\),实际使用应该用不到,这里只是记录一种思想
本以为可以使用对顶堆解决这个问题,但是搞错了对顶堆的应用场景,然后误打误撞的发现大根堆也可以解决
假设寻找的为第k小的数,遍历所有数,将小于堆顶的数据插入堆,并始终维护堆的大小为k,最终堆顶元素即为第k小的数
我总是担心更小的数据会将目标元素提前弹出堆,但这种情况是不会发生的,假设能够发生这种情况,那么说明被弹出的目标元素在升序序列中是第k位之前的,所以才会因为堆满而被弹出。因为目标元素就是第k小的,所以我们的假设错误。因为没有进入堆的元素在有序序列中均是第k位之后的,所以最终堆顶元素就是有序序列中前k位元素最大的元素,即第k小的元素
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
int kth_element(int a[], int l, int r, int k)
{
priority_queue<int> down; // 大根堆
for (int i = l; i <= r; ++ i)
{
if (down.empty() || a[i] < down.top()) down.push(a[i]);
if (down.size() > k) down.pop();
}
return down.top();
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i) cin >> a[i];
cout << kth_element(a, 1, n, k) << endl;
return 0;
}