The code is pretty self-explained enough...
When it comes to the Kth smallest:
algorithm2.png
algorithm.png
Note that the choosing of the pivot value is up to the programmer
class Solution {
public:
bool flag = false;
int findKthLargest(vector<int>& nums, int k) {
if (flag == false) {
k -= 1;
flag = true;
}
int pivot, pivotindex;
vector<int> larger, equal, smaller;
pivotindex = nums.size()/2; // generate a random number between 0 ~ num.size()
pivot = nums[pivotindex];
for (auto i : nums) {
if (i < pivot) {
smaller.push_back(i);
}
else if (i == pivot) {
equal.push_back(i);
}
else if (i > pivot) {
larger.push_back(i);
}
}
if (k < larger.size())
return findKthLargest(larger, k);
else if (k >= larger.size() && k < larger.size() + equal.size()) {
return pivot;
flag = false;
}
else if (k >= larger.size() + equal.size())
return findKthLargest(smaller, k-larger.size()-equal.size());
}
};
