Kth Smallest Element (with extra space)
#include <bits/stdc++.h>
using namespace std;
const int X = 3;
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) {
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;
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
|
|
|