= =...`消极怠工消极怠工, 240拖到最后一秒算是交掉了. w/e

找一个vector里第k大的数一直是个有意思的课题, 这次又碰到了, 自己写了一个. 记下来记下来, 以后八成用得到.

网上给的思路很多, 大家普遍认为用quicksort的algorithm是效率最好的. 原本也不怎么在乎效率问题, 完全是被240逼的啊啊啊啊啊...

vector好像并不是高效率的选择, 不过随它去吧`这次的tree实在有够恶心

#include <vector> 

int kTh(vector<int> & vals, int k){ 
    if(k == 0){ // 如果k为0, 则取中点 
        k = vals.size(); 
        k = k / 2 + k % 2; 
    }

    vector<int> v, l ,r; 
    int i; 
    v = vals; 
    int c, n = 0, s = v.size(), p = v[0]; // pivot = the first 

    while(true){ 
        for(i = s-1; i >= 0; i--){ // partite 
            c = v[i]; 
            if(c <= p) l.push_back(c); 
            else if(c > p) r.push_back(c); 
        } 
        s = l.size(); 
        if(s == k) break; // find the k'th 
        else if(s > k) v = l; // in left 
        else if(s < k) { // in right 
            k = k - l.size(); 
            v = r; 
        } 

        l.clear(); 
        r.clear(); 
        s = v.size(); 
        p = v[0]; // re-choose pivot 
    } 
    return p; 
}

欢迎大家批评指正...= =`

更新更规范的写法, 请见 CS 240复习总结之三: Sorting and Randomized Algorithms