《算法题讲解指南：优选算法-分治-快排》--45.数组中的第k个最大元素，46.最小的k个数
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--优选算法
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
45.数组中的第k个最大元素
题目链接：
215. 数组中的第K个最大元素 - 力扣（LeetCode）
题目描述：
题目示例：
解法(快速选择算法)：
算法思路：
在快排中，当我们把数组「分成三块」之后：[ left ，l ] [ l + 1，r - 1 ] [ r，right ]，我们可以通过计算每一个区间内元素的「个数」，进而推断出我们要找的元素是在「哪一个区间」里面。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。
C++算法代码：
class Solution { public: int Top_k(vector<int>& nums, int left, int right, int k) { if(left == right) { return nums[left]; } int l = left - 1, r = right + 1, i = left; //1、随机选择基准元素 int key = nums[rand() % (right - left + 1) + left]; //2、根据基准元素将数组分三块 while(i < r) { if(nums[i] > key) { swap(nums[i], nums[--r]); } else if(nums[i] < key) { swap(nums[i++], nums[++l]); } else { i++; } } //若右边区域元素个数>=k，说明第k大的数在右边区域，继续判断 if(right - r + 1 >= k) { return Top_k(nums, r, right, k); } //若右边区域个数<k,但中间加右边区域个数>=k，说明第k大的数在中间区域，则就是key else if(right - l >= k) { return key; } //若中间加右边区域个数<k，说明第k大的数在左边区域，继续判断 //对于整个数组第k大的数，在左边区域相当于是第(k-中间区域个数-右边区域个数)大的数 else { return Top_k(nums, left, l, k - (right - l)); } } int findKthLargest(vector<int>& nums, int k) { srand(time(NULL)); return Top_k(nums, 0, nums.size() - 1, k); } };算法总结及流程解析：
46.最小的k个数
题目链接：
LCR 159. 库存管理 III - 力扣（LeetCode）
题目描述：
题目示例：
解法(快速选择算法)：
算法思路：
在快排中，当我们把数组「分成三块」之后：[ l，left ] [ left + 1，right -1 ] [ right，r ]，我们可以通过计算每一个区间内元素的「个数」，进而推断出最小的k个数在哪些区间里面。
那么我们可以直接去「相应的区间」继续划分数组即可。
C++算法代码：
class Solution { public: vector<int> inventoryManagement(vector<int>& stock, int cnt) { // //解法一：快排(优点：简单无脑；缺点：时间复杂度很大O(NlogN)) // sort(stock.begin(), stock.end()); // vector<int> ret; // for(int i = 0; i < cnt; i++) // { // ret.push_back(stock[i]); // } // return ret; // //解法二：堆排序(优点：时间复杂度比快排小：O(Nlogk)；缺点：比较难想) // vector<int> ret; // if(cnt == 0) // { // return {}; // } // priority_queue<int> pq(stock.begin(), stock.begin() + cnt); // for(int i = cnt; i < stock.size(); i++) // { // if(pq.top() > stock[i]) // { // pq.pop(); // pq.push(stock[i]); // } // } // while(!pq.empty()) // { // ret.push_back(pq.top()); // pq.pop(); // } // return ret; //解法三：快速选择排序(优点：时间复杂度非常小：逼近O(N)；缺点：方法很巧妙很难想到) if(cnt == 0) { return {}; } srand(time(NULL)); Top_k(stock, 0, stock.size() - 1, cnt); return vector<int>(stock.begin(), stock.begin() + cnt); } void Top_k(vector<int>& nums, int left, int right, int cnt) { if(left == right) { return; } int key = nums[rand() % (right - left + 1) + left]; int l = left - 1, r = right + 1, i = left; while(i < r) { if(nums[i] > key) { swap(nums[i], nums[--r]); } else if(nums[i] < key) { swap(nums[i++], nums[++l]); } else { i++; } } if(l - left + 1 >= cnt) { return Top_k(nums, left, l, cnt); } else if(r - left >= cnt) { return; } else { return Top_k(nums, r, right, cnt - (r - left)); } } };算法总结及流程解析：
结束语
到此，45.数组中的第k个最大元素，46.最小的k个数 这两道算法题就讲解完了。45.数组中的第k个最大元素 通过随机基准元素将数组划分为三区（大于、等于、小于基准），根据各区元素数量递归查找目标区间，时间复杂度接近O(N)。46.最小的k个数 同样采用三区划分策略，通过计算各区元素数量直接定位目标区间，相比排序和堆方法更高效。希望大家能有所收获！
