剑指offer29题：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

首先必须注意的一点是：这道题不是考察数组的排序（所以解法1不推荐），如果N特别大的话，内存存不下；这道题正确解法是：找一个数据结构存储这K个数，如果后面的数大于这K个数的最大值，则把这个数和最大值替换。

解法一：

    //解法一：自己写的，冒泡排序
    //自己写的这个好像不是冒泡排序，有点像选择排序。。。。
    // vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    //     vector<int> result;
    //     if(input.empty() || k==0 || k>input.size())
    //     {
    //         return result;
    //     }
    //     //int min = input[0];
    //     for(int i=0;i<input.size();i++)
    //     {
    //         for(int j=i+1;j<input.size();j++)
    //         {
    //             if(input[j]<input[i])
    //             {
    //                 int temp;
    //                 temp = input[i];
    //                 input[i] = input[j];
    //                 input[j] = temp;
    //             }
    //         }
    //     }
    //     for(int i=0;i<k;i++)
    //     {
    //         result.push_back(input[i]);
    //     }
    //     return result;

    // }

解法2：

    //解法二：牛客大佬写的，用最大堆实现，堆的大小为K，不过调用了algorithml里的make_heap这些现成的函数
    //注意和解法四的区别
    // vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    // {

    //     if(input.empty() || k==0 || k>input.size())
    //     {
    //         return vector<int>{};
    //     }
    //     vector<int> result(input.begin(),input.begin()+k);
    //     make_heap(result.begin(),result.end());//建立最大堆
    //     for(int i=k;i<input.size();i++)
    //     {
    //         if(result[0]>input[i])
    //         {
    //             pop_heap(result.begin(),result.end());//把最大值移到最后一个元素
    //             result.pop_back(); //移除最后一个元素
    //             result.push_back(input[i]);
    //             push_heap(result.begin(),result.end()); //重新选出最大值
    //         }
    //     }
    //     sort_heap(result.begin(),result.end());
    //     return result;
    // }

解法3：

    //解法三：牛客大佬写的，利用自动排序的set这个数据结构，set大小为K，时间复杂度O（nlogk）
    //不能直接修改set容器内数据，所以只能删除某元素再插入要修改的数值。
    // vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    // {   
    //     if(input.empty() || k==0 || k>input.size())
    //     {
    //         return vector<int>{};
    //     }
    //     //仿函数中的greater<T>模板，从大到小排序，首元素为最大值
    //     multiset<int, greater<int> > leastNums;
    //     vector<int>::iterator vec_it=input.begin();
    //     for(;vec_it!=input.end();vec_it++)
    //     {
    //         //将前k个元素插入集合
    //         if(leastNums.size()<k)
    //             leastNums.insert(*vec_it);//插入这个元素，插入时候就排好序了！！！！！！！1
    //         else
    //         {
    //             //第一个元素是最大值
    //             multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
    //             //如果后续元素<第一个元素，删除第一个，加入当前元素
    //             if(*vec_it<*(leastNums.begin()))
    //             {
    //                 leastNums.erase(greatest_it);//删除首元素
    //                 leastNums.insert(*vec_it);//插入这个元素，插入时候就排好序了！！！！！！！1
    //             }
    //         }
    //     }   
    //     return vector<int>(leastNums.begin(),leastNums.end()); 
    // }

解法4：

    //解法四：牛客大佬写的，也是最大堆实现，不过没有用algorithm里的make_heap，而是自己y用vector实现最大堆并排序
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {   
        if(input.empty() || k==0 || k>input.size())
        {
            return vector<int>{};
        }
        vector<int> result;
        for(int i=input.size()/2-1;i>=0;i--)//建立堆
        {

            adjustHeap(input,i,k); //堆的大小为k
        }
        for(int i=k;i<input.size();i++)//将后面的数依次和K个数的最大值比较
        {
            if(input[0]>input[i])
            {
                int temp=input[i];
                input[i]=input[0];
                input[0]=temp;
                adjustHeap(input,0,k);
            }
        }
        for(int i=0;i<k;i++)
        { 
            result.push_back(input[i]);
        }          
        return result;      
    }
    void adjustHeap(vector<int>&input,int i,int n)//堆调整 n为length
    {
        int left = 2*i+1;  // i节点的左孩子
        int right = 2*i+2;   // i节点的右孩子
        int largest = i; //先设置父节点和子节点三个节点中最大值的位置为父节点下标
        if(left<n&&input[left]>input[largest])
        {
            largest = left;
        }
        if(right<n&&input[right]>input[largest])
        {
            largest = right;
        }
        if(largest!=i)  //最大值不是父节点，则进行交换
        {
            int temp;
            temp = input[i];
            input[i] = input[largest];
            input[largest] = temp;
            adjustHeap(input,largest,n); //递归调用，保证子树也是最大堆
        }
    }
    void heapSort(vector<int>&input,int length) //堆排序 这里没用到
    {
        for(int i=length/2-1;i>=0;i--)
        {//初始化堆

            adjustHeap(input,i,length);
        } 
        for(int i=length-1;i>0;i--)
        {
                int temp=input[i];
                input[i]=input[0];
                input[0]=temp;
            adjustHeap(input,0,i);

        }      
    }

};