topK 问题
topK问题主要有以上两类，例如求数组中第n大的数字，第n小的数字。或者是出现次数前n大的数字和出现次数前n小的数字。
大小根堆
利用大根堆过滤前top K 小的数据，利用小根堆过滤前 top K大的数据
快排分割
利用快排分割函数每次分割返回的基准数的位置，找出前top K 大或top K小的数据
大小根堆
使用大小跟堆的方式
求top K大的元素
求vec中前5小的元素
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <functional>
#include <unordered_map>
using namespace std;
int main()
{
vector<int> vec;
srand(time(NULL));
for (int i = 0; i < 1000; i++)
{
vec.push_back(rand() % 10000);
}
// 求vec中值最小的前5个元素
priority_queue<int> maxheap;
int k = 5;
// 由前k个元素构建一个大根堆
for (int i = 0; i < 5; i++)
{
maxheap.push(vec[i]);
}
// 遍历剩余的元素直到最后
for (int i = 5; i < vec.size(); i++)
{
if (maxheap.top() > vec[i])
{
maxheap.pop();
maxheap.push(vec[i]);
}
}
// 输出结果
while (!maxheap.empty())
{
cout << maxheap.top() << " ";
maxheap.pop();
}
cout << endl;
}
输出
Program returned: 0
Program stdout
17 16 16 10 2
求top K 重复次数最小的元素
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <functional>
#include <unordered_map>
using namespace std;
int main()
{
int k = 3;
vector<int>vec;
unordered_map<int, int> map;
srand(time(NULL));
for (int i = 0; i < 10000; i++)
{
vec.push_back(rand() % 1000);
}
for (auto key : vec)
{
map[key]++;
}
// 放入大根堆的时候，需要放key-value键值对
using Type = pair<int, int>;
using Comp = function<bool(Type&, Type&)>;
priority_queue<Type, vector<Type>, Comp> maxheap(
[](Type& a, Type& b)->bool {
return a.second < b.second;
});
auto it = map.begin();
for (int i = 0; i < k; i++, ++it)
{
maxheap.push(*it);
}
for (; it != map.end(); ++it)
{
if (maxheap.top().second > it->second)
{
maxheap.pop();
maxheap.push(*it);
}
}
while (!maxheap.empty())
{
cout << "key:" << maxheap.top().first
<< " cnt:" << maxheap.top().second << endl;
maxheap.pop();
}
}
输出
Program returned: 0
Program stdout
key:841 cnt:3
key:111 cnt:2
key:438 cnt:2
求top K 重复次数最大的元素
求vec中，前5个重复次数最多的元素
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <functional>
#include <unordered_map>
using namespace std;
int main()
{
int k = 3;
vector<int>vec;
unordered_map<int, int> map;
srand(time(NULL));
for (int i = 0; i < 10000; i++)
{
vec.push_back(rand() % 1000);
}
for (auto key : vec)
{
map[key]++;
}
// 放入大根堆的时候，需要放key-value键值对
using Type = pair<int, int>;
using Comp = function<bool(Type&, Type&)>;
priority_queue<Type, vector<Type>, Comp> minheap(
[](Type& a, Type& b)->bool {
return a.second > b.second;
});
auto it = map.begin();
for (int i = 0; i < k; i++, ++it)
{
minheap.push(*it);
}
for (; it != map.end(); ++it)
{
if (minheap.top().second < it->second)
{
minheap.pop();
minheap.push(*it);
}
}
while (!minheap.empty())
{
cout << "key:" << minheap.top().first
<< " cnt:" << minheap.top().second << endl;
minheap.pop();
}
}
输出
Program returned: 0
Program stdout
key:305 cnt:20
key:672 cnt:21
key:201 cnt:22
快排分割
求 top K大的元素
#include<iostream>
using std::cin;
using std::cout;
/*
快排分割函数
*/
int Parttation(int* nums, int begin, int end)
{
int val = nums[begin];
int i = begin;
int j = end;
while (i < j)
{
while (i<j && nums[j]>val)
j--;
if (i < j) {
nums[i] = nums[j];
i++;
}
while (i < j && nums[j] < val)
i++;
if (i < j) {
nums[j] = nums[i];
j--;
}
}
nums[i] = val;
return i;
}
void seleteTopK(int* nums, int begin, int end, int k) {
int pos = Parttation(nums, begin, end);
if (pos == k - 1)
{
return;
}
else if (pos > k - 1)
{
// 再次递归快排分割
seleteTopK(nums, begin,pos - 1, k);
}// 再次对右边进行快排分割
else {
seleteTopK(nums, pos+1, end, k);
}
}
int main()
{
int arr[] = { 10,5,4,12,12,3,1,2 };
seleteTopK(arr, 0, sizeof arr / sizeof arr[0] - 1, 3);
for (int i = 0; i < 3; i++)
cout << arr[i] << ' ';
cout << std::endl;
}
输出
1 3 4
D:\Project file\for\x64\Debug\for.exe (进程 24220)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .
