Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
1
odws
Lekhana.R 123454766
TwoMax
Test 14(2020)
Backpack with recursion
Dar
CirclQ
CutRod(BottomUp)
NumType