地址: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;
    }
};


Leetcode      Leetcode C++

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!