小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录45.数组中的第k个最大元素题目链接题目描述题目示例解法(快速选择算法)算法思路C算法代码算法总结及流程解析46.最小的k个数题目链接题目描述题目示例​编辑解法(快速选择算法)算法思路C算法代码算法总结及流程解析结束语45.数组中的第k个最大元素题目链接215. 数组中的第K个最大元素 - 力扣LeetCode题目描述题目示例解法(快速选择算法)算法思路在快排中当我们把数组「分成三块」之后[ left l ] [ l 1r - 1 ] [ rright ]我们可以通过计算每一个区间内元素的「个数」进而推断出我们要找的元素是在「哪一个区间」里面。那么我们可以直接去「相应的区间」去寻找最终结果就好了。C算法代码class Solution { public: int Top_k(vectorint 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(vectorint nums, int k) { srand(time(NULL)); return Top_k(nums, 0, nums.size() - 1, k); } };算法总结及流程解析46.最小的k个数题目链接LCR 159. 库存管理 III - 力扣LeetCode题目描述题目示例解法(快速选择算法)算法思路在快排中当我们把数组「分成三块」之后[ lleft ] [ left 1right -1 ] [ rightr ]我们可以通过计算每一个区间内元素的「个数」进而推断出最小的k个数在哪些区间里面。那么我们可以直接去「相应的区间」继续划分数组即可。C算法代码class Solution { public: vectorint inventoryManagement(vectorint stock, int cnt) { // //解法一快排(优点简单无脑缺点时间复杂度很大O(NlogN)) // sort(stock.begin(), stock.end()); // vectorint ret; // for(int i 0; i cnt; i) // { // ret.push_back(stock[i]); // } // return ret; // //解法二堆排序(优点时间复杂度比快排小O(Nlogk)缺点比较难想) // vectorint ret; // if(cnt 0) // { // return {}; // } // priority_queueint 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 vectorint(stock.begin(), stock.begin() cnt); } void Top_k(vectorint 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个数 同样采用三区划分策略通过计算各区元素数量直接定位目标区间相比排序和堆方法更高效。希望大家能有所收获