题解 | #寻找第K大#

寻找第K大

http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

1.partition算法

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        K = K-1;
        int p = -1;
        int start=0,end = a.size()-1;
        while(true) {
            p = partition(a,start,end);
            if(p==K) {
                return a[K];
            }
            if (p<K){
                start = p+1;
            } else {
                end = p-1;
            }
        }
    }
    

    int partition(vector<int>& a,int start,int end) {
        if(start>=end) {
            return start;
        }
        int x = a[end];
        int i = start-1;
        for(int j=start;j<end;j++){
            if(a[j] > x ) {
                i++;
                swap(a[i],a[j]);
            }
        }
        swap(a[i+1],a[end]);
        return i+1;
    }
};

全部评论

相关推荐

07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务