网站google排名出现过几分钟,网站建设教学视频百度云盘,建设企业银行怎么转账,房地产新闻解法#xff1a;快速选择算法
说明#xff1a;堆排序也是经典解决问题的算法#xff0c;但时间复杂度为#xff1a;O(NlogK)#xff0c;K为k个元素
而将要介绍的快速选择算法的时间复杂度为: O(N)
先看我的前两篇文章#xff0c;分别学习#xff1a;数组分三块#…
解法快速选择算法
说明堆排序也是经典解决问题的算法但时间复杂度为O(NlogK)K为k个元素
而将要介绍的快速选择算法的时间复杂度为: O(N)
先看我的前两篇文章分别学习数组分三块随机选择基准值的思想。会的话直接看就完事了 解惑
1.a,b,c是什么意思 a,b,c分别是key, key, key 所代表的区间中值的个数
2.如何判断 看落在哪个区间a区间全是key的所以如果落在这个区间说明k就在a这个区间因此就只在这个区间递归即可。 而如果 a b k 说明k a了也就是说不仅在a区间一定也包含b这个区间而b都是 key的所以此时直接返回即可无需继续递归。 如果都不是说明k a b了所以肯定也落进了c区间而因为现在我们跳过了 ab 个元素所以要找的其实是剩下的k - b - c个元素继续递归即可。
3.返回值 函数的返回值要求是一个vector而经过上面的分析k个元素绝对是在一个区间中的所以即便递归结束后数组是乱序只要从[0,k]大小的区间内所有值都符合最小的k个元素题目也说了可以以任意顺序返回,那结果就是直接返回递归后的[nums.begin(),nums.begin()k]即可。
附上完整代码
class Solution
{
public:vectorint smallestK(vectorint nums, int k) {srand(time(nullptr));qselect(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin() k};}void qselect(vectorint nums,int l,int r,int k){if(l r)return ;int key GetRandomkey(nums,l,r);int left l-1,right r1;for(int i l;inums.size();){if(nums[i] key)swap(nums[left],nums[i]);else if(nums[i] key)i;else if(nums[i] key){if(i right)break;swap(nums[--right],nums[i]);}}int a left - l 1,b right - left - 1;if(a k)return qselect(nums,l,left,k);else if(a b k)return;else return qselect(nums,right,r,k - a - b);}int GetRandomkey(vectorint nums,int l,int r){int random rand();return nums[random % (r - l 1) l];}};
