[215] 数组中的第K个最大元素
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/description/
- algorithms
- Medium (64.59%)
- Likes: 992
- Dislikes: -
- Total Accepted: 298.5K
- Total Submissions: 462.1K
- Testcase Example: ‘[3,2,1,5,6,4]\n2’
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和
k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和
k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
方法1: 快速查找算法
第K问题, 可以使用快速查找算法
1. 我的算法
class Solution {
public:
int quick_select(vector<int> & nums, int left, int right){
int pivotkey = rand() % (right - left) + left; //随机选择
swap(nums[pivotkey], nums[left]);
int pivot = nums[left];
while(left < right){
while(left < right && nums[right] <= pivot) --right;
nums[left] = nums[right];
while(left < right && nums[left] >= pivot) ++left;
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
int findKthLargest(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1, mid = 0, target = k - 1; // target 指第k大的数的索引
while(left < right){
mid = quick_select(nums, left, right);
if(mid == target){
return nums[mid];
} else if (mid < target){
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums[left];
}
};
经测试, 随机选取 pivotkey
会极大的提高效率
随机选择前:
随机选择后:
复杂度分析:
- 时间复杂度:
O(n)
, 由于随机选择pivotkey
, 故不会出现 $O(n^2)$ 的最坏情况 - 空间复杂度:
O(1)