Topk算法_topn算法
大家好，又见面了，我是你们的朋友全栈君。
topK算法
思路1：快速选择算法 可以采用快速选择算法，借助快排，设mid为每次划分中间结果,每次划分完之后如果mid==k，则说明序列刚刚好，第k位置和他前面的位置都是前K大的数，如果mid < k，则说明第K大的元素在后半部分，则前半部分肯定是前K大的数，只需从后半部分找k – mid大的数即可，否则如果mid > k，则说明第K大的数在前半部分，只需从前半部分找前K大的数字即可。 时间复杂度：假设每次划分的mid都在中间，每层都只是对一半做划分,所以每次划分的数据量为 n,n/2,n/4,n/8…一共有logn层，根据等比数列可以算出来时间复杂度为O(n) C++代码演示
#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
int partion(int l,int r,int a[]){
int x = a[l];
while(l < r){
while(l < r && a[r] < x)r --;
if(l < r)a[l ++] = a[r];
while(l < r && a[l] > x)l ++;
if(l < r)a[r --] = a[l];
}
a[l] = x;
return l;
}
int quickSort(int l,int r,int a[],int k){
if(l < r){
int mid = partion(l,r,a); //划分结果
int ls = mid - l + 1; //[l,mid]一共有多少数
if(ls == k)return; //如果划分的mid恰好就是第K大的数
if(ls < k)quickSort(mid + 1,r,a,k - ls); //如果第K大的数在后半部分
else quickSort(l,mid - 1,a,k); //如果第K大的数在前半部分
}
}
int main(){
int a[] = {
3,2,3,1,2,4,5,5,6};
int k = 4;
quickSort(0,8,a,k);
for(int i = 0;i < k;i ++)
cout<<a[i]<<" ";
return 0;
}思路2：堆排序 可以建立一个大小为K的小顶堆,每次把当前数和小顶堆的堆顶作比较，如果当前数字大，则替换掉堆顶，重新调整堆。 时间复杂度：调整堆为O(logK)，所以总的时间复杂度为nlog(K)
C++代码
#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
priority_queue<int,vector<int>,greater<int> >pq; //默认是大顶堆
int main(){
int k = 3;
int a[] = {
3,1,5,2,4,3};
for(int i = 0;i < 3;i ++)pq.push(a[i]);
for(int i = 3;i < 6;i ++){
if(pq.top() < a[i]){
pq.pop();
pq.push(a[i]);
}
}
while(!pq.empty()){
cout<<pq.top()<<endl;
pq.pop();
}
return 0;
}对比 堆方案只需要开辟K个数组空间即可，而且不需要变动原数组，而随机选择需要改原数组，如果不改动的话就需要创建一个O(n)的数组
leetcode例题 原题链接 数组中的第K个最大元素 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
题解 1.快速选择版本
class Solution {
public:
int partion(int l,int r,vector<int>&nums){
int x = nums[l];
while(l < r){
while(l < r && nums[r] < x)r --;
if(l < r)nums[l ++] = nums[r];
while(l < r && nums[l] > x)l ++;
if(l < r)nums[r --] = nums[l];
}
nums[l] = x;
return l;
}
void quickSort(int l,int r,vector<int>&nums,int k){
if(l < r){
int mid = partion(l,r,nums);
int lnum = mid - l + 1; //[l,mid]一共有多少个数
if(k == lnum)return;
if(k < lnum)quickSort(l,mid - 1,nums,k);
else quickSort(mid + 1,r,nums,(k - lnum));
}
}
int findKthLargest(vector<int>& nums, int k) {
quickSort(0,nums.size() - 1,nums,k);
return nums[k - 1];
}
};2.优先队列版本
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int> >pq;
for(int i = 0;i < k;i ++)pq.push(nums[i]);
for(int i = k;i < nums.size();i ++){
if(pq.top() < nums[i]){
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录