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问题快排思想的全部内容，希望文章能够帮你解决TopK问题快排思想所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。