剑指offer29最小的K个数

剑指offer29

1、普通排序和堆排序
普通排序--直接vector用sort，时间复杂度O(nlog(n)),空间复杂度O(1)
堆排序
（1）multiset或者set

Class Person
{
public:
    String name;
    int age;
    Perosn(String name1,int age1):name(name1),age(age1){}

}
Class cmp //仿函数
{
public:
     bool operator()(const Person &p1,const Person &p2) const
     {
           return p1.age<p2.age;
     }
}
set<int>s; //默认升序
set<int,less<int>>s;//升序，等同默认
set<int,greater<int>>s;//降序：
set<Person,cmp>s;//自定义类型，cmp为仿函数

（2）multimap或者map

map<T1,T2> m;//参数1：key值，参数2：value值，默认按照key的升序排列元素
map<T1,T2,less<T1> > m; //升序，等同上
map<T1,T2,greater<T1>> m;  //该容器是按key的降序排列元素
map<Person,Person,cmp> m; //自定义类型，写仿函数，其实此时map也可以不写仿函数，如下用
map<int,Person>m; //直接用插入元素的age作为键值
Person p1("Lee",30);
m.insert(pair<int,Person>(p1.age,p1)); //直接用age作为键值排序

（3）priority_queue

priority_queue<int>q; //默认大顶堆
priority_queue<int,vector<int>,less<int>>q;//大顶堆，等同默认
priority_queue<int,vector<int>,greater<int>>q;//小顶堆：

个人代码

class Solution {
public:
    #define Ator multiset<int>::iterator
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>v;
        multiset<int>s;//默认升序,即multiset<int,less<int>>,降序multiset<int,greater<int>>
        if(k>input.size())
            return v;
        for(int x:input)
            s.insert(x);
        int index=0;
        for(Ator it=s.begin();it!=s.end()&&index<k;it++,index++) //复制前k个数到v
            v.push_back(*it);
        return v;
    }
};

2、快排简化此题

牛客参考讲解

个人代码

class Solution {
public:
    int partition(vector<int> &input,int l,int r) //排序数组[l,r]之间元素
    {
        int key=input[r]; //选择基准
        int index=l; //index最终会表示基准的正确位置，index之前[l,index)小于key,index之后(index,r]大于key
        for(int i=l;i<r;i++)
        {//循环未完成之前，index位置元素始终会是大于key的元素，因为小于key的会使得index++，置于index之前
            if(input[i]<key)//如果小于基准，与index元素交换，index位置后移，使得小于基准元素至于index之前
            {
                swap(input[i],input[index]);
                ++index;
            }
        }
        swap(input[index],input[r]);
        return index;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>v;
        if(input.empty()||k>input.size()||k<0)
            return v;
        //若得出快速排序中某个标准的位置index=k或者index=k-1都可以轻易前k个小的数[0----index-1]或者[0---index]
        //二分思想
        int l=0;
        int r=input.size()-1;
        while(l<=r)
        {
            int index=partition(input,l,r);
            if(index==k||index==k-1) //前k个元素都能确定
                return vector<int>(input.begin(),input.begin()+k);//匿名对象，拷贝构造，不包括末尾的左闭右开
            else if(index>k) //大了
            {
                r=index-1;
            }
            else if(index<(k-1))
            {
                l=index+1;
            }
        }
        return v;
    }
};