题目描述
N个数据 i=K,K+1,K+2…N 长度的子序列中求出第K大的值
输入样例1
3 2
1 2 3
输出样例1
1
2
算法1
动态存储+二分查找
思路:
当 i=K时 其实就是求最小值 i=K+1时 求倒数第二个值 依次类推
时间复杂度
Nlog2N+?
我总体就遍历一遍N 然后每次寻找插入点时log2N
但这个代码最后 超时2个样例 可能是vector的插入那里花了很多时间 导致超时 但我也不清楚vector的插入的时间复杂段 希望有大佬帮我解答下
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
vector<int> ve;
int main()
{
int n,k;
cin>>n>>k;
n-=k;
int x;
while(k--){
scanf("%d",&x);
ve.push_back(x);
}
sort(ve.begin(),ve.end());
int i=0;
int min_x=ve[i++];
n=n+1;
while(n--){
printf("%d\n",min_x);
scanf("%d",&x);
if(x>=min_x){ //发现如果x<min_x 发现不会对答案有任何的影响
ve.insert(lower_bound(ve.begin(),ve.end(),x),x); //用lower找地址
min_x=ve[i++]; //当有新的值插入进动态 那么min_x就要往后移动(但值不一定改变)
}
}
return 0;
}
算法2
用桶排去做
后面我再次读题 发现他Pi的值是小于等于N的 N<=5e5 所以可以用桶排来写 如果Pi的值属于int的类型的话 可能要离散或者map映射了
时间复杂度
全部遍历一遍 N 然后再从桶排里面找到需要的值 最坏情况是N 因为输出的值不会比之前小 所以参考双指针的时间复杂度
2N
参考文献
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=5e5+5;
int a[maxn];
int main()
{
int n,k,min_x=0x3f3f3f3f;
cin>>n>>k;
int x;
for(int i=0;i<k;i++){
cin>>x;
min_x=min(min_x,x);
a[x]++;
}
a[min_x]--; //用过就减去 不然会卡住
printf("%d\n",min_x);
for(int i=k;i<n;i++){
cin>>x;
if(min_x<x){
a[x]++;
for(int j=min_x;j<maxn;j++){ //类似双指针的写法
if(a[j]!=0){
min_x=j;
break;
}
}
a[min_x]--;
}
printf("%d\n",min_x);
}
}
算法3
堆排
用优先队列进行操作
时间复杂度
NlogK
参考文献
官方文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,K; cin >> N >> K;
vector<int> P(N);
for(int i=0; i<N; i++) cin >> P[i];
priority_queue<int,vector<int>,greater<int> > que;
for(int i=0; i<K; i++) que.push(P[i]);
cout << que.top() << endl;
for(int i=K; i<N; i++){
if(que.top() < P[i]){
que.pop();
que.push(P[i]);
}
cout << que.top() << endl;
}
}