多语言网站一个域名网站友链

解法：快速选择算法

说明：堆排序也是经典解决问题的算法，但时间复杂度为：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区间，而因为现在我们跳过了 a+b 个元素，所以要找的其实是剩下的k - b - c个元素！继续递归即可。

3.返回值

        函数的返回值要求是一个vector，而经过上面的分析，k个元素绝对是在一个区间中的，所以即便递归结束后数组是乱序，只要从[0,k]大小的区间内所有值都符合最小的k个元素，题目也说了可以以任意顺序返回,那结果就是直接返回递归后的[nums.begin(),nums.begin()+k]即可。

附上完整代码：

class Solution 
{
public:vector<int> smallestK(vector<int>& nums, int k) {srand(time(nullptr));qselect(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin() + k};}void qselect(vector<int>& nums,int l,int r,int k){if(l >= r)return ;int key = GetRandomkey(nums,l,r);int left = l-1,right = r+1;for(int i = l;i<nums.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(vector<int>& nums,int l,int r){int random = rand();return nums[random % (r - l + 1) + l];}};