链接
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
耗时
解题：30 min
题解：18 min
题意
在数组中找到第 k 大的元素。
思路
快排的思想。
将第一个数作为基准数，将比基准数大的放在基准数的前面，将比基准数小的放在基准数的后面。然后看 k 是在基准数的前面还是后面，或者正好在基准数的位置。如果正好在基准数的位置，则已经得到了第 k 大元素，直接输出；如果是在基准数的前面或者后面，则缩小范围至基准数的前面或者后面，继续上述操作直至 k 正好是基准数的位置或者等缩小范围至范围内仅有一个元素。
最坏情况下是
O
(
n
2
)
O(n^2)
O(n2)，期望是
O
(
n
)
O(n)
O(n)。
AC代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
if(n == 1) return nums[0];
int l = 0, r = n-1;
int p = l, ans = -1;
while(r-l+1 > 1) {
while(l < r) {
while(l < r && nums[r] <= nums[p]) r--;
while(l < r && nums[l] >= nums[p]) l++;
swap(nums[l], nums[r]);
}
swap(nums[p], nums[r]);
if(k-1 == r) {
break;
}
if(k-1 > r) {
l = r+1;
r = n-1;
p = l;
}
else {
l = 0;
r = r;
p = l;
}
}
return nums[k-1];
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
