# quick select and median-finding, deterministic O(n) time

• For explanations, see https://en.wikipedia.org/wiki/Median_of_medians
Just for fun.

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size(), low = 0, high = n - 1;
if(n == 0) return -1; //empty case
while(low < high){
int mid = partition(nums, low, high);
if(mid < k - 1)
low = mid + 1;
else if(mid > k - 1)
high = mid - 1;
else return nums[mid];
}
return nums[high];
}
int partition(vector<int>& nums, int l, int r){
if(r <= l) return l;
int pvt = pivot(nums, l, r);
for(int j = l; j <= r; j++)
if(nums[j] == pvt){
std::swap(nums[j], nums[l]);
break;
}
int i = l + 1;
for(int j = i; j <= r; j++)
if(nums[j] > pvt)
std::swap(nums[j], nums[i++]);
std::swap(nums[l], nums[i - 1]);
return i - 1;
}
int pivot(vector<int>& nums, int l, int r){
if(r - l < 5)
return nums[median5(nums, l, r)];
vector<int> temp;
for(int i = l; i <= r; ){
int right = min(r, i + 4);
int med = median5(nums, i, right);
temp.push_back(nums[med]);
i = right + 1;
}
return findKthLargest(temp, ( (int)temp.size() + 1) / 2);
}
int median5(vector<int>&nums, int l, int r){
vector<int> temp;
for(int i = l; i <= r; i++){
int j;
for(j = 0; j < temp.size(); j++){
if(temp[j] >= nums[i]) break;
}
temp.insert(temp.begin() + j, nums[i]);
}
for(int i = l; i <= r; i++)
if(nums[i] == temp[(l+r)/2]) return i;
return l;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.