快速排序的变种——快速选择算法
给出一个数组，例如[1,4,2,6,8,3]，现在要求出第 k 大的数字，即将数组从大到小排列，选择第k个数。用什么算法更快找到这个数？
最容易想到的就是先将数组排序，就可以很容易找到第 k 大的数字。就算用快速排序，时间复杂度为 O(nlgn)。有没有更快的算法？
快速排序每次将数组分成两部分，升序排列时，左半部分元素都大于右半部分元素，假设某次划分结果如下，中间元素下标为 mid，如果 k==mid，表示 mid 就是最终结果。如果 k>mid，说明结果在右半部分中，如果 k<mid，说明结果在左半部分。这就表明，我们划分完之后，只需再接着处理其中一半就可以，快速排序需要处理左右两部分。基于这个思想，我们将其称为快速选择算法。
快速选择算法 时间复杂度 O(n) 空间复杂度 (O(lgn))
数组中的第K个最大元素
详细题解
我的 AC 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
int quickSelect(vector<int>& nums,int l,int r,int k){
int mid = partion(nums,l,r);
if(mid==k)
return nums[mid];
if(k<mid)
return quickSelect(nums,l,mid-1,k);
else
return quickSelect(nums,mid+1,r,k);
}
int partion(vector<int>& nums,int l,int r){
random(nums,l,r);
int key = nums[l];
while(l<r){
while(l<r && nums[r]<=key){
--r;
}
nums[l] = nums[r];
while(l<r && nums[l]>=key){
++l;
}
nums[r] = nums[l];
}
nums[l] = key;
return l;
}
inline void random(vector<int>& nums,int l,int r){
int R = rand() % (r-l+1)+l;
swap(nums[l],nums[R]);
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
int len = nums.size();
return quickSelect(nums,0,len-1,k-1);
}
};
|
关于快速排序的详细分析：快速排序分析及优化
