牛客网剑指offer第29题——最小的k个数

题目：

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

分析：

思路一：我们可以利用STL库的sort函数，先将数组排序（时间复杂度O（nlogn），再选前K个数。

代码如下：

 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>res;
        if(k == 0 || input.size() == 0 || k > input.size())
            return res;
        sort(input.begin(),input.end());
        for(int i =0;i < k;i++)
            res.push_back(input[i]);
        return res;

代码很简单，而又朴实无华。

但是很明显有些浪费，因为我们并不关心其余N-K个元素的顺序，上述做法反而做了多余的工作。

那么更好的思路是：采用快速排序的思想：找前K个值。

毫无疑问的是，快速排序的思想是很朴素的：让正确的元素出现在正确的位置：什么意思？就是：如果一个数；它前面的所有元素都小于它（我们并不关心它前面的元素是否拍好序），其后面额元素都大于它，那么这个数就处在正确的位置；举例：3 1 2 4 7 9 6，对于数字4，它前面的元素都小于它，它后面的元素都大于它，因此4出于正确的位置（正确的位置的含义是：即使这个数组完全排好序，这个数的位置索引仍然是不变的）。那么上述问题就变成了：我们让一组数据的前K个数，使得他们都处在一个正确的位置。

 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>res;
        if(k == 0 || input.size() == 0 || k > input.size())
            return res;
        int start =0;
        int end = input.size()-1;
        int bounder = partition(input,start,end);
        while(bounder != k-1)
        {
            if(bounder  < k-1)
                start = bounder+1;
           else
                end = bounder-1;
            bounder = partition(input,start,end);
        }
        for(int i =0;i < k;i++)
            res.push_back(input[i]);
        return res;
    }
       int partition(vector<int>& input, int l,int r)
        {
            int tmp = input[l];
            while(l < r)
            {
                while( l < r && input[r] > tmp) r--;
                swap(input[l],input[r]);
                while(l < r && input[l] <= tmp) l++;
                swap(input[l],input[r]);
            }
            input[l] = tmp;
            return l;
        }

解释代码：

第20——32行的代码：称之为partition,其作用是：对于一个随机的数组vector，我们处理其最左端的数据。也就是input[0],最终使得input[0]处在一个正确的位置（也就是让其前面的数比它小，后面的数比它大），并返回这个位置。

我们来解读一下：这个位置bounder表达的含义：这个位置前的数都比这个位置的数小，后面的数都比它大；换句话说：前面的bounder-1个是就是这个数组前bounder-1个最小的数！！！

现在主程序也就是第2行到第18行的代码，如果bounder大于k了，说明bounder前面的数多于k个，很明显我们要缩小partition的范围；而bounder小于k，说明bounder前面的数还不够k个，我们需要进一步搜索。总而言之，我们需要使得找到的bounder正好使得bouder 前面的数和bounder处的数。一共有k个。