TopK问题快排思想

本文主要是介绍TopK问题快排思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入格式为：
-23 17 -7 11 -2 1 -34
2
输入为第k大的数

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int partition(vector<int> &data,int low,int high){int m=low;int ran=data[high];for(int i=low;i<high;i++){if(data[i]>=ran) {swap(data[i],data[m++]);}}swap(data[m],data[high]);return m;
}int findKmax(vector<int> &data,int low,int high ,int k){int p;int index=-1;if(low<high){p=partition(data,low,high);int len= p-low+1;if(len==k){index=p;}else if(len<k){index=findKmax(data,p+1,high,k-len);}else{index=findKmax(data,low,p-1,k);} }return index;
}
int main(){int a,k;vector<int> data;while(scanf("%d",&a)!=EOF){data.push_back(a);}k=data.back();data.pop_back();int index=findKmax(data,0,data.size()-1,k);cout<<data[index];
}

这篇关于TopK问题快排思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---