面试中常见的经典算法题：O(n)算法查找第k大的数。
O(n)算法查找第k大的数
思路
这里讲利用快速排序Partion的算法，核心思想是快排的分支算法，具体思路：
- 利用快排的partion函数将数组分成左右两个部分
- 如果位置p刚好等于k，则说明p位置的数，就是我们要找的数，如果分出来的边界位置p小于给定的数k，我们知道最小的第k个数，肯定在p的右边，如果p大于给定的k则在p边界的左边
- 递归在p的左边或者右边查找
注：p为数组下标需要加1。
具体的细节可以查看《算法导论》第九章，下面是简单的实现代码。
复杂度
对于快速排序，算法复杂度是O(N * logN)。而这个算法的算法复杂度是O(N)。为什么呢？
其实这个地方的算法复杂度分析很有意思。
第一次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂度是O(N * logN)（可以这么理解，每次交换用了N，一共logN次）。
但是这里在确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。
也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)。？
接下来的过程是1+1/2+1/4+…….. < 2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。
代码
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int partion(vector<int> &nums,int k,int start, int end){
int tmp = nums[start], n = nums.size(), left = start, right = end;
while(left < right){
while(right > left && nums[right] < tmp) right --;
if(right > left)
nums[left ++] = nums[right];
while(left < right && nums[left] >= tmp) left ++;
if(left < right)
nums[right --] = nums[left];
}
nums[left] = tmp;
if(left == k - 1) return tmp;
else if(left > k - 1) return partion(nums, k, start, left - 1);
else return partion(nums, k, left + 1, end);
}
int findKthLargest(vector<int>& nums, int k) {
return partion(nums, k, 0, nums.size() - 1);
}
};
|
非递归实现
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
| static auto sycn_false = [](){
ios :: sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int start = 0, end = nums.size() - 1;
while(start <= end){
int tmp = nums[start], left = start, right = end;
while(left < right){
while(left < right && nums[right] < tmp)
right --;
if(left < right){
nums[left ++] = nums[right];
}
while(left < right && nums[left] >= tmp)
left ++;
if(left < right){
nums[right --] = nums[left];
}
}
nums[left] = tmp;
if(left == k - 1) return nums[left];
else if(left > k - 1) end = left - 1;
else start = left + 1;
}
return -1;
}
};
|
