Kth Smallest Element (with extra space), C++ (gcc)

Kth Smallest Element (with extra space)

#include <bits/stdc++.h>

using namespace std;

const int X = 3;
// O(N) <- V.size()
int median (vector<int>& v) {
    int n = v.size();
    if (n < X) {
        sort(v.begin(), v.end());
        return v[n/2];
    }
    vector<int> new_v;
    for (int j = 0; j < n; j += X) {
        vector<int> cur;
        int last = (j+X-1 < n)? j+X-1 : n-1;
        
        for (int i = j; i <= last; i ++) cur.push_back(v[i]);
        sort(cur.begin(), cur.end());
        
        new_v.push_back(cur[(last - j + 1)/2]);
    }
    return median(new_v);
}

// 
int foo (int l, int r, vector<int>& v, const int K) { // log(N) - O(r - l + 1)
    if (l == r) return v[l];
    
    vector<int> cur;
    for (int j = l; j <= r; j ++) cur.push_back(v[j]);
    
    int L = l, R = r;
    int med = median(cur);
    
    while (l <= r) {
        while (l <= r && med >= v[l]) l ++;
        while (l <= r && med <  v[r]) r --;
        if (l <= r) {
            swap(v[l], v[r]);
            l ++; 
            r --;
        }
    }
    
    int M = r;
    // 5 <- (M - L + 1) | 5th
    if ((M - L + 1) >= K) return foo (L, M, v, K);
    else return foo (M+1, R, v, K-(M-L+1));
}

int main(){
    
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development