原题链接
解法1:对原数组进行快速排序,然后 O(1)输出。
关于sort:
Sort函数包含在头文件为#include<algorithm>的c++标准库中(因此既然可以直接用为何要手写?)
同时,此函数有三个参数:
(1)第一个是要排序的数组的起始地址。
(2)第二个是结束的地址(最后一位要排序的地址)
(3)第三个参数是排序的方法,具体写法见代码,同时可以不写第三个参数,此时默认的排序方法便是从小到大。
时间复杂度为O(n log2 n)
#include<bits/stdc++.h>
using namespace std;
/*
bool cmp(int x,int y){
return x<y;
}
从小到大*/
int n,a[1000001];
int main(){
int i,k;
cin>>n>>k;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1/*,cmp*/);
cout<<a[k];
}
解法2:根据快排思想来寻找第 k 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改:因为每次递归都会将数组划分为三部分,而答案只会在这三部分中的一个,不需要再对其他部分进行搜索,从而达到优化时间复杂度(O(n))的效果。
具体代码其他题解已经写的很清楚了,这里便不在赘述。
解法3:直接调用函数nth_element
在强大的STL库中存在一个神奇的函数,那就是nth_element,这个函数主要用来将数组元素中第k小的整数排出来并在数组中就位,随时调用,可谓十分实用。
函数语句:nth_element(数组名,数组名+第k小元素,数组名+元素个数)
具体如何用见下面代码(最短):
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000001],i;
int main(){
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i];
nth_element(a,a+k,a+n);
cout<<a[k];
}
解法4:基数排序!
首先,我们了解一下基数排序是什么。
顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,
基数排序法是属于稳定性的排序,其时间复杂度为O(n logr m)其中r为所采取的基数,而m为堆数,
在某些时候,基数排序法的效率高于其它的稳定性排序法。——来自 百度百科
其实就是说,n个数,i从1开始,以第i位为关键字,申请一个长度为r的桶,
每个桶装对于a数组每个处于r进制的第i位,再把这些桶装的数按照入桶顺序倒出来,链接到一起.
这么处理一直到i处于a 数组最大值处于r进制的最高位,按照装桶法排序.
排完最高位,最后的按照这样排出来的数据一定是有序的。
大概代码长这样:
queue<int>w[16];
int a[200001],t,n;
int pow16(int i){return 1<<(4*i);}
void radixsort(){
For(j,1,8){
t=0;
For(i,1,n)w[a[i]/pow16(j-1)%16].push(a[i]);
For(i,0,15)while(w[i].size())a[++t]=w[i].front(),w[i].pop();
}
}
完结撒花!✿✿ヽ(゚▽゚)ノ✿
还有,建议出个加强版,把数据范围改为n<5000000,可以卡掉sort!
我知道各位大佬一定有比我更好的方法,欢迎吊打,QAQ!(光速逃)