Top K 问题常见形式:
给10万个单词,找第K大词频的单词
给10玩个数,找第K大的数
方法1: 使用堆
建堆 时间复杂度为 O(n) , 堆排序 为 O(logn) , 那么堆初始化的时间复杂度 是 nlog(n)
使用c++ 标准库 priority_queue(默认建大堆) 大堆降序
int main()
{
priority_queue<int> pq;
pq.push(10);
pq.push(8);
pq.push(6);
pq.push(4);
pq.push(2);
cout << pq.top() << endl;
for (int i = 0; i < 5; i++)
{
cout << pq.top() << endl;
pq.pop();
}
return 0;
}
自己 实现 堆排序
#include <iostream>
#include <vector>
using namespace std;
vector<int> heapv;
// 向下调整
void heapdown(int parent, int n)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && heapv[child] > heapv[child + 1])
child++;
if (heapv[parent] > heapv[child])
{
swap(heapv[parent], heapv[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
// 堆排序
void heapsort()
{
int n = heapv.size();
// 建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
heapdown(i, n);
}
// 排序
while (n > 1)
{
swap(heapv[0], heapv[n - 1]);
heapdown(0, --n);
}
}
int main()
{
heapv = {4, 10, 3, 5, 1};
heapsort();
cout << "排序后的数组:";
for (const auto &num : heapv)
{
cout << num << " ";
}
cout << endl;
return 0;
}
方法2:使用快排
使用库函数 std::sort
int main()
{
vector<int> v = {4, 10, 3, 5, 1};
sort(v.begin(), v.end());
cout << "升序排序后的数组:";
for (int i : v)
{
cout << i << " ";
}
cout << endl;
sort(v.begin(), v.end(),[](int a,int b){ return a > b;});
cout << "降序序排序后的数组:";
for (int i : v)
{
cout << i << " ";
}
cout << endl;
return 0;
}
自己实现快排
vector<int> v;
void quitsort(int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int key = left;
while (begin < end)
{
while (begin < end && v[begin] <= v[key])
begin++;
while (begin < end && v[end] >= v[key])
end--;
swap(v[begin], v[end]);
}
swap(v[key], v[begin]);
key = end;
quitsort(left,key-1);
quitsort(key+1,v.size());
}
int main()
{
v = {4, 10, 3, 5, 1};
int n = v.size(), right = n - 1, left = 0;
quitsort(left, right);
for (int i : v)
{
cout << i << " ";
}
cout << endl;
return 0;
}