[剑指Offer]40-最小的k个数

题目链接

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

输入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个

使用红黑树实现以上算法。
特别地，由于直接替换节点可能破坏红黑树的结构，所以红黑树不支持直接改变元素值，必须要删除旧值、插入新值来实现。

代码

法一代码

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;
    }
};

[剑指Offer]40-最小的k个数

题目链接

题意

解题思路

相关知识

红黑树

比较仿函数greater 与less (即可以当作函数一样使用)

最大堆

代码

法一代码

法二代码