Skip to content

Instantly share code, notes, and snippets.

@byshen
Last active April 9, 2019 04:35
Show Gist options
  • Save byshen/a30004432b099c161edbe9d53f813f66 to your computer and use it in GitHub Desktop.
Save byshen/a30004432b099c161edbe9d53f813f66 to your computer and use it in GitHub Desktop.
#include <vector>
#include <iostream>
using namespace std;
int partition(vector<int>& vec, int left, int right) {
int pivot = vec[left];
int l = left + 1;
int r = right;
while (l<=r) {
if (vec[l] > pivot && vec[r] < pivot) {
std::swap(vec[l], vec[r]);
l++;
r--;
}
if (vec[l] <= pivot) {
l++;
}
if (vec[r] >= pivot) {
r--;
}
}
std::swap(vec[r], vec[left]);
cout <<vec[r] <<endl;
return r;
}
int findK(vector<int>& vec, int k) {
int left = 0;
int right = vec.size()-1;
int kth;
while(left <= right) {
int idx = partition(vec, left, right);
if (idx == k) {
kth = idx;
break;
}
if (idx > k) {
right = idx - 1;
}
if (idx < k) {
left = idx + 1;
}
}
return vec[kth];
}
int findPercent(vector<int> vec, double percent) {
if (percent <0 || percent >1.0) {
throw range_error("Invalid percent");
}
if (vec.size() == 0) {
throw length_error("Invalid vector length");
}
int n = vec.size();
int k = (int) (n*percent);
if (k==n) k=k-1;
vector<int> vcopy(vec.begin(), vec.end());
return findK(vcopy, k);
}
int main() {
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(4);
v.push_back(2);
v.push_back(5);
try {
cout << findPercent(v, 0.5)<<endl;
}
catch (exception & e) {
cerr << e.what() <<endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment