Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note：
You may assume k is always valid, 1 ≤ k ≤ array's length.
思路：
- 按从大到小全排序，然后取第k个元素，时间复杂度O(nlogn)，空间复杂度O(1)
- 利用堆进行部分排序。维护一个大根堆，将数组元素全部压入堆，然后弹出k次，第k个就是答案。时间复杂度O(klogn)，空间复杂度O(n)
- 选择排序，第k次选择后即可得到第k大的数，时间复杂度O(nk)，空间复杂度O(1)
- 堆排序，维护一个k大小的小根堆，将数组中的每个元素与堆顶元素进行比较，如果比堆顶元素大，则删除堆顶元素并添加该元素，如果比堆顶元素小，则什么也不做，继续下一个元素。时间复杂度O(nlogk)，空间复杂度O(k)。
- 利用快速排序中的partition思想，从数组中随机选择一个元素x，把数组划分为前后两部分sa和sb，sa中的元素小于x，sb中的元素大于或等于x。这时有两种情况：
sa的元素个数小于k，则递归求解sb中的第k-|sa|大的元素
sa的元素个数大于或等于k，则递归求解sa中的第k大的元素
时间复杂度O(n)，空间复杂度O(1)思路4和5比较高效，可以接受，其他思路太慢了，不采纳。
思路4：快排
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];
}
};
思路5：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();
}
};