选取TOP K的问题之快速排序
2023-04-18 15:22:16 时间
- 问题:选取数组中最小的前k个数,见剑指 Offer 40. 最小的 k 个数(基于快速排序的数组划分,清晰图解) - 最小的k个数 - 力扣(LeetCode)
方法1:快速排序:
- 哨兵划分:选取一个哨兵,将大于哨兵的移到哨兵右侧;小于哨兵的移到哨兵左侧。
- 递归操作:递归的将左右子数组进行哨兵划分,直至区间长度为1,完成递归。
- 快排完成后将数组前k个值输出
void quicksort(vector<int>&arr,int l,int r){ if(r<=1) return; int i = l;int j = r; while(i<j){ while(i<j && arr[j] >= arr[l]) --j; while(i<j && arr[i] <= arr[l]) ++i; swap(arr[i],arr[j]); } swap(arr[l],arr[i]); quicksort(arr,l,i-1); quicksort(arr,i+1,r); }
l和r是数组的左右边界;
时间复杂度:O(Nlog N); 空间复杂度:O(log N)最好;O(N)最坏
方法2:基于快速排序的数组划分
核心思想:因为返回的值不要求排序,只需要找出最小的前k个值就行。所以不再对左右两个子数组都进行递归操作,而是根据 k的值 与每次递归之后的 i值进行比较,若大于i,则说明前 第 k+1 个最小值在右子数组,小于i,则说明 第k+1个最小值在左子数组,若相等,则说明是 arr[k]即为第k+1个最小值,直接返回前k个值。
class{ public: vector<int> getLeastNumbers(vector<int>&arr,int k){ if(k>=arr.size()) return arr; return quicksort(arr,k,0,arr.size()-1); } private: vector<int> quicksort(vector<int>& arr,int k,int l ,int r){ int i = l, j = r; while(i<j){ while(i<j && arr[j] >= arr[l]) --j; while(i<j && arr[i] <= arr[l]) ++i; swap(arr[i],arr[j]); } swap(arr[i],arr[l]); if(k > i) return quicksort(arr,k,i+1,r); if(k < i) return quicksort(arr,k,l,i-1); vector<int>v; v.assign(arr.begin(),arr.begin()+k); return v; } };
时间复杂度:等比数列求和,O(N); 空间复杂度:O(log N)。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击