题目描述
输入n个整数,找出其中最小的k个数。
注意:
数据保证k一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;
样例
输入:[1,2,3,4,5,6,7,8] , k=4
输出:[1,2,3,4]
算法1
(快速选择) $O(klogn)$
运用快速排序的思想,每次快速选择会将一个数放置到正确的位置(即满足左边的数都比它小,右边的数都比它大),因此我们可以对原数组做k次快速选择。
时间复杂度分析:一次快速选择的时间复杂度是$O(logn)$,进行k次,时间复杂度为$O(klogn)$
C++ 代码
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
for(int i = 1;i <= k;i++)
res.push_back(quick_select(input,0,input.size()-1,i));
return res;
}
int quick_select(vector<int>& q,int l,int r,int k)
{
if(l >= r) return q[l];
int i = l-1,j = r+1,x = q[l+r >> 1];
while(i < j)
{
do i++;while(q[i] < x);
do j--;while(q[j] > x);
if(i < j) swap(q[i],q[j]);
}
if(k <= j-l+1) return quick_select(q,l,j,k);
else return quick_select(q,j+1,r,k-(j-l+1));
}
};
算法2
(堆排序) $O(nlogk)$
维护一个大小为k的大根堆,将数组元素都push进堆,当堆中的数大于k时弹出堆顶元素。注意弹出堆顶的顺序是从大到小的k个数,要进行逆序操作
时间复杂度分析:建堆的时间复杂度是$O(logk)$,要进行n次建堆的操作。
C++ 代码
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
priority_queue<int> heap;
for(auto x : input)
{
heap.push(x);
if(heap.size() > k) heap.pop();
}
while(heap.size())
{
res.push_back(heap.top());
heap.pop();
}
reverse(res.begin(),res.end());
return res;
}
};
额,快排超时啊
这种写法的快排会超时(在letcode里),因为每轮都要通过快排递归一遍添加一个数,k轮,复杂度为O(kN)
应该直接快排一次得到有序序列然后for输出前k个数即可
lc上不要求从小到大输出,acwing里快选+结果排序的话是复杂度是O(n+klogk)?
是的,理论上比堆小点
快速选择是O(n)
第二个直接定义小根堆不就行了
两行搞定
哈哈哈世界上的另外一个我
时间复杂度是O( kn)
class Solution {
public:
vector[HTML_REMOVED] getLeastNumbers_Solution(vector[HTML_REMOVED] input, int k) {
sort(input.begin(),input.end());
vector[HTML_REMOVED] a(input.begin(),input.begin()+k);
return a;
}
};
快速选择的复杂度不是O(n)吗
我感觉也是O(n)
快排的时间复杂度最坏是O(n^2),最好是O(nlogn)
假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少log(N+1)次,最多N次。
1. 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。
2. 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。
快速选择,不是排序,选择不需要的另一边不用管
class Solution {
public:
vector[HTML_REMOVED] getLeastNumbers_Solution(vector[HTML_REMOVED] input, int k) {
sort(input.begin(),input.end());
input.resize(k);
return input;
}
};
不应该快排完直接按照序号输出吗,为什么要进行k次快选,舍近求远了
全部快排结束,需要执行的次数,比选出前k个需要执行的次数要多。
假如有100个数,k=70 。我只需要排出前70个,而你需要全部排序100个。
第四个形参有什么用?
sort(input.begin(), input.end());
vector[HTML_REMOVED] res;
for(int i=0;i<k;i++) {
res.push_back(input[i]);
}
return res;
第一个时间复杂度是错误的
这里能不能用单调栈来做呢?
直接return 数组。这个代码是不是好一点。
if(k>j)
quickchoose(input,j+1,r,k);
return quickchoose(input,l,j,k);
赞
快速选择的复杂度是$O(n)$吧,所以第一个应该是$O(nK)$这个复杂度就要比$O(nlogK)$要高。
我也在纳闷,要知道哪些数大于标准数,哪些数小于标准数,不得全部遍历过才能知道吗
赞同
第一次看到C++中还有do这种关键字?
do while循环吧
C++就是语法丰富呀。do while和while还有点小差别。