求n个数中最小的K个数。

思路一：如果可以改变原数组，则可利用快排的思想。

1 先用Partition将数组分为俩部分然后比较与K-1的大小

2 若大于k-1 则调整尾端，，若小于k-1，则调整头端，再利用partition直到返回等于k-1。

代码：

   vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        int length=input.size();
        if(k<=0||k>input.size())
            return result;
        if(k==input.size())
            return input;
        int start=0;
        int end=length-1;
        int index=Partition(input,start,end);
        while(index!=k-1){
            if(index>k-1){
                end=index-1;
                index=Partition(input,start,end);
            }else{
                start=index+1;
                index=Partition(input,start,end);
            }
        }
        for(int i=0;i<k;i++)
            result.push_back(input[i]);
        return result;
    }
    int Partition(vector<int> &input,int start,int end){
        int index=input[start];
        while(start<end){
            while(start<end && input[end]>=index)
                end--;
            if(start<end)
                input[start]=input[end];
            while(start<end && input[start] <= index)
                start++;
            if(start<end){
                input[end]=input[start];
            }
        }
        input[start]=index;
        return start;
    }

思路二：

利用STL库的红黑树存储，不改变原有的数据，用一个大小为K的Multiset，如果树中的数据小于K个则直接插入，若set满了，则找出其中最大的然后与要插入的数据比较，若插入的数据大直接丢弃，否则删除set里最大的数，将新数据插入。本示例用大根堆

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        multiset<int,greater<int> > leastNumbers;
        leastNumbers.clear();
        if(k<=0 || k>input.size())
            return vector<int>();
        if(k==input.size())
            return input;
        for(int i=0;i<input.size();i++){
            if(leastNumbers.size()<k){
                leastNumbers.insert(input[i]);
            }else{
                if(input[i]<*(leastNumbers.begin())){
                    leastNumbers.erase(leastNumbers.begin());
                    leastNumbers.insert(input[i]);
                }
            }
        }
        vector<int> result(leastNumbers.begin(),leastNumbers.end());
        return result;
    }“