Topk算法_topn算法

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…一

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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();
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168776.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CentOS7查看和关闭防火墙

    CentOS7.0默认使用的是firewall作为防火墙查看防火墙状态firewall-cmd–state停止firewallsystemctlstopfirewalld.service禁止firewall开机启动systemctldisablefirewalld.service转自:CentOS6和CentOS7防火墙的关闭关闭se…

  • 【Python_环境配置】Pycharm创建虚拟环境

    【Python_环境配置】Pycharm创建虚拟环境问题由来从github下载的模型程序,所适包的版本不同,导致Pycharm中包混乱、版本冲突。 为每个程序单独创建虚拟环境,使得特定程序只能访问虚拟环境中的包,从而保持全局解释器的干净整洁。创建虚拟环境File-Settings-PythonInterpreter-设置图标,后续设置如下:Pycharm之创建虚拟环境在特定虚拟环境中安装包1、选择下方Terminal2、利用cd进入项目的Scripts文件夹3、输入activate4、利用pip命…

    2022年10月30日
  • java vo 什么意思_在Java中VO , PO , BO , QO, DAO ,POJO是什么意思

    java vo 什么意思_在Java中VO , PO , BO , QO, DAO ,POJO是什么意思在Java中VO,PO,BO,DAO,POJO是什么意思最近在项目中,遇到VO,我的天。。。那就一起学习回忆一下首先简单说明下:O/RMapping是ObjectRelationalMapping(对象关系映射)的缩写。简单来说,就是将对象和关系数据库绑定,用对象来表示关系数据。JavaWEB三层架构咱们更需要熟练使用VO:值对象(ValueObject)用new关键字创建…

  • 三星ODIN刷机包的修改

    三星ODIN刷机包的修改SunnyOK系列讲座索引【第一讲】如何用Odin刷机-新手必读http://bbs.gfan.com/android-1653492-1-1.html【第二讲】I897卡刷或CWM刷机教程http://bbs.gfan.com/android-1701867-1-1.html【第三讲】APK应用程序的解包、修改、编辑、打包及应用http://bbs

  • 数据挖掘十大经典算法个人总结

    数据挖掘十大经典算法个人总结数据挖掘十大经典算法个人总结这两年对数据挖掘相关知识研究运用的已经很多了,最近看了关于数据挖掘十大经典算法的文章。想对其进行一个总结,强化下自己对这些算法的理解。1.C4.5C4.5是基于ID3算法改进的决策树算法。相对于ID3,其伪代码:它具有的特点:1)用信息增益率来选择属性信息增益会偏向选择取值多的属性,而信息增益率除以H(v)来削弱

  • Windows Server 2012 R2 Microsoft Windows HTTP.sys远程代码执行漏洞 (MS15-034)(CVE-2015-1635)

    Windows Server 2012 R2 Microsoft Windows HTTP.sys远程代码执行漏洞 (MS15-034)(CVE-2015-1635)一、漏洞情况二、整改记录

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号