[剑指Offer]40-最小的k个数
2024-10-02 19:01:08
题目链接
题意
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的四个数字是1,2,3,4,
解题思路
法一：若可以修改输入数据：时间复杂度O(n)。
利用快排的partition数组。第一遍以后partion的范围要想清楚，"是一个小小的范围"，这样才能实现时间复杂度O(n)。
注意：1、特判一定要全！2、瞎throw容易看不到真正的错误提示... 3、各种边界填写的变量要过脑子...
法二：若不可以修改输入数据，或是要处理海量数据(内存较小)：时间复杂度O(nlogk)，内存要求可容纳大小为k的数组即可。
- 可以维护一个大小为k的数组。
- 容器满了后，每次再来一个数，若大于容器内最大值，则删除、插入新值（即替换），若小于容器内最大值，则忽略。
- 最终得到的数组k即是最小的k个
使用红黑树实现以上算法。
特别地，由于直接替换节点可能破坏红黑树的结构，所以红黑树不支持直接改变元素值，必须要删除旧值、插入新值来实现。
相关知识
红黑树
红黑树是特殊的二叉查找树，红黑节点保证最长路径<=2*最短路径。红黑树是自动有序的。
红黑树不严格满足二叉平衡树(AVL)左右子树高度最多相差1的条件。？具体
红黑树的查找、插入、删除时间复杂度都是O(logk)。？具体
STL中的set和multiset都是用红黑树实现，其中multiset可有重复元素。
比较仿函数greater 与less (即可以当作函数一样使用)
- 在
typedef multiset<int,greater<int>> intSet中，greater实质是一个结构体，greater表示内置类型从大到小排序，less表示内置类型从小到大排序。它们也可以用作sort函数的比较器。 - set与multiset中默认使用less,即由小到大排序。
最大堆
最大堆中，根结点的值总是大于它的子树中任意节点的值。
得到最大值O(1)、插入、删除时间复杂度都是O(logk)。
代码
法一代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> minNums;
if(input.size()!=0&&k>=1&&k<=input.size()){//!!!写全
size_t beg=0;
size_t end=input.size()-1;
size_t index=partition(input,beg,end);//
while(index!=k-1){//
if(index<k-1){
beg=index+1;//
index=partition(input,beg,end);//
}
else{
end=index-1;//
index=partition(input,beg,end);//
}
}
for(int i=0;i<k;i++){
minNums.push_back(input[i]);
}
}
return minNums;
}
private:
size_t partition(vector<int> &input,size_t beg,size_t end){
if(!input.size()||end<beg||beg<0){
throw "input error!";
}
size_t index=random(beg,end);
swap(input[index],input[beg]);//
int temp=input[beg];
size_t i=beg;
size_t j=end;
while(i<j){
while(i<j&&input[j]>=temp){
--j;
}
if(i!=j){
input[i]=input[j];
++i;
}
while(i<j&&input[i]<=temp){
++i;
}
if(i!=j){
input[j]=input[i];
--j;
}
}
input[i]=temp;
return i;
}
void swap(int& a,int& b){
int temp=a;
a=b;
b=temp;
}
size_t random(size_t beg,size_t end){
if(end<beg){
throw "input error!";
}
srand((unsigned) time(0));
return beg+rand()%(end-beg+1);
}
};
法二代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> minVec;
typedef multiset<int,greater<int>> intSet;
intSet minSet;
if(input.size()&&k>0&&k<=input.size()){
for(auto it=input.begin();it!=input.end();++it){
if(minSet.size()!=k){
minSet.insert(*it);
}
else{
if(*minSet.begin()>*it){
minSet.erase(minSet.begin());
minSet.insert(*it);
}
}
}
}
for(auto it=minSet.begin();it!=minSet.end();++it){
minVec.push_back(*it);
}
return minVec;
}
};
最新文章
- 配置Report Server超时
- sql join 优化
- Annotation
- libevent 安装异常
- Android5.0新特性——Material Design简介
- IT架构之IT架构模型——思维导图
- HBase总结（十二）Java API 与HBase交互实例
- sicily 1099 Packing Passengers
- 收敛 p75
- 404、500、502等HTTP状态码介绍
- 本地yum服务搭建
- 浅谈js中的正则表达式
- 重构前VS重构后效果对比
- 【翻译】在Ext JS和Sencha Touch中创建自定义布局
- ros 运行rviz时出现 QXcbConnection: XCB error: 148 错误 解决方法
- win10更改hosts文件
- INDY10的IDHttpServer应答客户端
- arcpy调试
- 20145207 Exp9 web安全基础实践
- Android 布局之LinearLayout 子控件weight权重的作用详析