Leetcode 面试题40.最小的k个数【C++】

地址：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

题目

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

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解题思路

这个题思路来的挺快的，不过肯定不是最好的办法了。看完题目我就想到了对数组进行排序，然后从小到大取 k 个数出来就好了。

然后我就按着这个思路写了一个反向的冒泡排序，把最小的数从后往前冒泡，最后就会得到一个从小到大的数组，之所以反向冒泡，是因为题目要求要找的是最小的 k 个数，所以我就想到把最小的数先冒泡求出来，就可以将其加入到数组 min 中保存，然后由于只需要返回最小的k个数，所以只要得到了最小的k个数，就可以返回结果，剩下的元素就没必要再排序了。顺利地写出来下面的代码~

需要注意考虑特殊情况，如果题目没有做限制的话，我们是需要考虑数组 arr[] 的大小小于 k 的情况的，但是题目已经说明了 0 <= k <= arr.length <= 10000 ，也就是说前述的情况不可能存在。但 k 可以取到 0 ，显然这个时候返回的应该是一个空数组；还有一种“特殊”情况是 k == arr.size() ，虽然不把它作为特殊情况程序也没问题，但是这种情况下显然返回值就是原数组，没必要对其进行排序，然后逐个取最小的数再构造一个数组。

存在的缺陷：考虑到上述 k == arr.size() 的情况后，我又想到了个问题，按照我的解题思路，如果 k 相对于数组 arr[] 的大小比较小的话，那只需要对少量的k个数排序就能得到结果，但如果 k 相对于数组 arr[] 的大小很大的情况下，如果 arr[] 中有9个元素，而 k == 8 ，那这种情况下就要对八个数进行排序，代价就更大了。

改进思路：有一个小改进思路，首先对判断 k < arr.size()/2 ，如果为 true，那就从小往大对较少的k个数排序就可以得到结果；如果为 false ，则反过来从大到小对 arr.size() - k 个数排序，然后剩下没排序的k个数即要返回的结果。

代码（原始思路）

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> min;//返回值
        //k <= arr.length，如果k为0则直接返回空数组
        if (k == 0)
            return min;
        //如果k刚好等于arr的大小，则直接返回原数组arr
        if (arr.size() == k)
            return arr;
        //冒泡排序，把最小的数从后往前冒泡
        for (int i = 0; i < arr.size(); i++) {
            for (int j = arr.size() - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }
            }
            min.push_back(arr[i]);
            //只要找到了k个数就可以不再继续往下找
            if (min.size() == k)
                break;
        }
        return min;
    }
};