文章目录
- 1 快排减而治之（O(N)）
- 1 小根堆（ O(NlogK)）
- 2 快排（O(NlogN)）
1 快排减而治之（ O ( N ) O(N) O(N)）
使用快排思想，但每次取出pivot后，只排其中一半，有主定理证明时间复杂度为 O ( N ) O(N) O(N)，空间复杂度 O ( 1 ) O(1) O(1)
代码语言：javascript复制class Solution {
public:
int partition(vector<int>& nums, int left, int right) {
int i = left, j = right;
int pivot = rand() % (right - left 1) left;
swap(nums[left], nums[pivot]);
int pos = nums[left];
while (i < j) {
while (nums[j] >= pos && i < j) j--;
while (nums[i] <= pos && i < j) i ;
if (i < j) swap(nums[i], nums[j]);
}
swap(nums[left], nums[i]);
return i;
}
int findKthLargest(vector<int>& nums, int k) {
int size = nums.size();
int targetidx = size - k; // 第k大元素在升序数组中的索引
int left = 0, right = size - 1;
while (true) {
int pivot = partition(nums, left, right);
if (pivot == targetidx)
return nums[pivot];
else if (pivot < targetidx)
left = pivot 1;
else if (pivot > targetidx)
right = pivot - 1;
}
return -1;
}
};1 小根堆（ O ( N l o g K ) O(NlogK) O(NlogK)）
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> q;
for (auto& val : nums)
if (q.size() == k && q.top() < val) {
q.pop();
q.emplace(val);
} else if (q.size() < k)
q.emplace(val);
return q.top();
}
};
2 快排（ O ( N l o g N ) O(NlogN) O(NlogN)）
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1];
}
};
