题目要求输入n个无序的数,要求你从这n个数中找到第k小的数字什么,并输出。
这里有三种算法可以实现:
先进行排序,在进行取最第k小的数字。
利用数据结构的最小堆来实现依次获取第k小的数字。
利用快速排序的思路来进行寻找第k小。
先排序,再输出第k小的数字
如果学过排序算法就比较好办,用快速排序和归并排序时间复杂度都能到o(nlogn)。如果没有学过排序算法,也没有关系的,我们c++里面有algorithm头文件,里面可以调用sort排序函数来直接排序。下面为了节省代码,就直接用sort来排序。
#include<iostream>
#include<algorithm>
const int N=1e6+5;
int a[N],n,k;
signed main(){
//加快cin cout的读入和输出,不能与printf混用
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
//读入数据
std::cin>>n>>k;//n 个数,第k小
for(int i=1;i<=n;++i) std::cin>>a[i];
std::sort(a+1,a+n+1);//调用algorithm排序
std::cout<<a[k];
return 0;
}
优点:代码可以非常的简洁,适用一组数据多次输出不同k。
缺点:时间复杂度较大。
利用数据结构的最小堆来进行排序
要了解堆这种优先队列。如果是第一小的数,我们就取一次最小堆顶部元素。第k小,我们需要取k次顶部。
#include<iostream>
#include<algorithm>
const int N=1e6+5;
int a[N],n,k;
int size;//最小堆的有效数
void init(){//初始化堆
for(int i=size/2;i>0;--i) down(i);
}
void down(int p){//向下调整堆
int c=p<<1;//p为父节点,c为子节点
while(c<=size){
if(c+1<=size&&a[c+1]<a[c]) ++c;
if(a[c]<a[p]) std::swap(a[c],a[p]);
else break;
p=c;
c<<=1;
}
return;
}
int get_min(){//取最小堆顶部
std::swap(a[1],a[size--]);
down(1);
return a[size+1];
}
void solve(){
//读入
std::cin>>n>>k;
for(int i=1;i<=n;++i) std::cin>>a[i];
size=n;//设置堆大小
init();//初始化堆
int res;//所求结果
while(k--){
res=get_min();//取k次最小堆顶部
}
std::cout<<res;
}
signed main(){
//加快cin cout的读入和输出,不能与printf混用
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
solve();
return 0;
}
优点:如果k比较小的话,速度是比较快的,但是代码的量就比较大,并且要对堆很熟悉。
缺点:如果k比较打的话,时间复杂度是o(nlogn)。
利用快排的思想来取出第k小的数
先来带你温习一下快排函数
void quick_sort(int q[],int l,int r){
if(l>=r) return;
int flag=q[l+r>>1],i=l-1,j=r+1;
while(i<j){
do ++i;while(q[i]<flag);
do --j;while(q[j]>flag);
if(i<j) std::swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
在快速排序的时候我们发现j为一个分界点,下标<=j标就说<=flag;
如过下标>j,就说数字>flag;
于是我们就有一种优化的方法来选择是一次快排的左边还是右边。
#include<iostream>
#include<algorithm>
const int N=1e6+5;
int a[N],n,k;
int rs(int a[],int l,int r,int k){//快排的优化选择
if(l>=r) return a[l];
int i=l-1,j=r+1;
int flag=a[(l+r)>>1];
while(i<j){
do ++i;while(a[i]<flag);
do --j;while(a[j]>flag);
if(i<j) std::swap(a[i],a[j]);
}
if(k<=j) return rs(a,l,j,k);
else return rs(a,j+1,r,k);
}
void solve(){
std::cin>>n>>k;
for(int i=;i<n;++i) std::cin>>a[i];
std::cout<<rs(a,1,n,k);//数组,初始下标为1,n个数,第k小
}
signed main(){
//加快cin cout的读入和输出,不能与printf混用
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
solve();
return 0;
}
优点:可以把时间优化到o(n)
缺点:你得学会手搓快排