O(n)算法查找第k大的数

文章目录
  1. 1. O(n)算法查找第k大的数
    1. 1.1. 思路
    2. 1.2. 复杂度
    3. 1.3. 代码
      1. 1.3.1. 递归实现
      2. 1.3.2. 非递归实现


面试中常见的经典算法题:O(n)算法查找第k大的数。

O(n)算法查找第k大的数

思路

这里讲利用快速排序Partion的算法,核心思想是快排的分支算法,具体思路:

  1. 利用快排的partion函数将数组分成左右两个部分
  2. 如果位置p刚好等于k,则说明p位置的数,就是我们要找的数,如果分出来的边界位置p小于给定的数k,我们知道最小的第k个数,肯定在p的右边,如果p大于给定的k则在p边界的左边
  3. 递归在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;
}
};

本文总阅读量

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×