# C++ solutions: O(nlgk) by Min-Heap and O(n) by partition

• Solution 1: O(nlgk) by using min-heap

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
size_t len = nums.size();
if(len < k) return 0;

priority_queue<int, std::vector<int>, std::greater<int>> q;
for(auto &v : nums)
{
if(q.size() < k)
{
q.push(v);
}
else if (v > q.top())
{
q.pop();
q.push(v);
}
}
return q.top();
}
};
``````

Solution 2: O(n) by partitioning recursively

``````class Solution {
public:
int partition(vector<int>& nums, int i, int j)
{
if (i == j) return i;

int pivot = nums[i];
std::swap(nums[i], nums[j]);

int i0 = i;
for(int k = i; k < j; k ++)
{
if(nums[k] <= pivot)
{
std::swap(nums[k], nums[i0 ++]);
}
}
std::swap(nums[i0], nums[j]);
return i0;
}
int findKthLargest(vector<int>& nums, int k)
{
size_t len = nums.size();
int pi = 0;
int tgt = len - k;

int a = 0, b = len - 1;
while((pi = partition(nums, a, b)) != tgt)
{
if(pi < tgt)
{
a = pi + 1;
}
else if(pi > tgt)
{
b = pi - 1;
}
}
return nums[pi];
}
};``````

• Thanks for sharing, your first solution could be simplified as:

``````int findKthLargest(vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> q;
for (auto &v : nums) {
q.push(v);
if (q.size() > k) {
q.pop();
}
}
return q.top();
}
``````

• Thanks.
Really smart method!

• @lanshan317
Actually it's not the same. We should avoid adding the value to the heap if it's smaller than the top and size == k.

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