# 16ms C++ solution using partition

• ``````class Solution {
// this function tries to find the proper pivot by comparing 3 elements in the vector
// which helps improve the efficiency
void handlePivot(vector<int>& nums, int left, int right) {
int mid = (left + right) / 2;
if (mid == left) return;
if (nums[left] > nums[mid] && nums[left] > nums[right]) {
if (nums[mid] > nums[right]) swap(nums[left], nums[mid]);
else swap(nums[left], nums[right]);
}
else if (nums[left] < nums[mid] && nums[mid] > nums[right]) {
if (nums[left] < nums[right]) swap(nums[left], nums[right]);
}
else {
if (nums[left] < nums[mid]) swap(nums[left], nums[mid]);
}
}
int partition(vector<int>& nums, int left, int right) {
if (left == right) return left;
int l = left + 1, r = right;
handlePivot(nums, left, right);
int pivot = nums[left];
while (true) {
while (l <= r && nums[l] >= pivot) ++l;
while (nums[r] < pivot && r >= l) --r;
if (l >= r) break;
swap(nums[l++], nums[r--]);
}
swap(nums[left], nums[l - 1]);
return l - 1;
}
public:
int findKthLargest(vector<int>& nums, int k) {
if (k > nums.size() || k <= 0 || nums.size() == 0) return 0;
int left = 0, right = nums.size() - 1;
while (left <= right) {
int pos = partition(nums, left, right);
if (pos == k - 1) return nums[pos];
if (pos < k - 1) left = pos + 1;
else right = pos - 1;
}
return nums[left];
}
};
``````

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