Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
quickselect
#include<bits/stdc++.h> using namespace std; int part(vector<int>&v,int pivot,int lo,int hi) { int i=lo; int j=lo; while(j<hi) { if(v[j]<=pivot) { swap(v[i],v[j]); i++; j++; } else if(v[j]>pivot) { j++; } } swap(v[i],v[j]); return i; } int qs(vector<int>&v,int lo,int hi,int k,int n) { int pivot=v[hi]; int pi=part(v,pivot,lo,hi); if(k<pi) { return qs(v,lo,pi-1,k,n); } else if(k>pi) { return qs(v,pi+1,hi,k,n); } else { return v[pi]; } } int main() { int t; cin>>t; while(t--) { int n; cin>>n; vector<int>v(n); for(int i=0;i<n;i++) { cin>>v[i]; } int k;cin>>k; cout<<qs(v,0,n-1,k-1,n)<<endl; } return 0; }
run
|
edit
|
history
|
help
0
single_digit
operator++
runtime template mode processor
sample
Dar
c++ car racing game
a
aa
Quiz 12/13
Wipro Problem 1: generate roll number