讯享网

作者 | 小夕       责编 | 欧阳姝黎

题目

输入整数数组 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

小夕：这道题还有另外一种解法就是计数排序，先说一下什么是计数排序吧

计数排序

计数排序动画

计数排序文字版

• 初始化，计数数组的下标count都是等于0.，意味着每个元素都出现了0次。
• 第一个元素2，放在下标是2的位置，由于只出现了一次，所以下标为2的count值+1.
• 第2个元素2，放在下标是2的位置，计数count再进行+1 变成2，代表2出现了2次。
• 第3个元素1，放在下标是1的位置，下标为1的计数count进行+1变成1，代表1出现了1次。

  

• 第4个元素0，放在下标是0的位置，下标为0的计数count进行+1变成1，代表0出现了1次。
• 第5个元素1，放在下标是1的位置，下标为1的计数count进行+1变成2，代表1出现了2次。
• 第6个元素5，放在下标是5的位置，下标为5的计数count进行+1变成1，代表5出现了1次
• 接下来针对计数数组进行处理，遍历计数数组，为了方便理解把原数组清空。
• 遍历索引为0，计数数组值是1，代表0出现1次，所以让0占位原数组的1位。
• 遍历索引为1，计数数组值是2，代表1出现2次，所以让1占位原数组的2位。
• 遍历索引为2，计数数组值是2，代表2出现2次，所以让2占位原数组的2位。
• 遍历索引为3，计数数组值是0，代表3出现0次，所以不占位
• 遍历索引为4，计数数组值是0，代表4出现0次，所以不占位
• 遍历索引为5，计数数组值是1，代表5出现1次，所以5占位原数组1位。
• 到这里。原数组变得有序了！

使用计数排序解题

解题动画

计数排序解题图解

代码

Java

class Solution {     public int[] getLeastNumbers(int[] arr, int k) {         if (k == 0 || arr.length == 0) {             return new int[0];         }         // 统计每个数字出现的次数         int[] counter = new int[10001];         for (int num: arr) {             counter[num]++;         }         // 根据counter数组从头找出k个数作为返回结果         int[] res = new int[k];         int idx = 0;         for (int num = 0; num < counter.length; num++) {             while (counter[num]-- > 0 && idx < k) {                 res[idx++] = num;             }             if (idx == k) {                 break;             }         }         return res;     } } 

C++

讯享网class Solution { public:     vector<int> getLeastNumbers(vector<int>& arr, int k) {         vector<int> temp(10000);  //arr中的值不会大过10000也不会小于0，所以申请一个10000大小的整形数组         for(const int& val : arr)  //数组下标val对应arr中的值为val的数，temp[val]对应arr中只为val的个数             ++temp[val];         vector<int> result;  //要返回的结果         int count = 0;  //计数         for(int i = 0; i < temp.size(); ++i)  //从前向后遍历temp，即为从小到大遍历val         {             if(count >= k)  //要返回的结果中储存的数大于等于k，跳出循环                 break;                         if(temp[i])  //temp[i]不为0，说明该处有数据             {                 while(temp[i]--)  //arr中有几个值为i数据就往result中放几个                 {                     result.push_back(i);                     count++;  //计数                 }             }         }         result.resize(k);         return result;     } }; 

Python

def get_least_numbers(arr, k):     nums = [0] * 10000  # 申请一个包含最大值个数的元素     for a in arr:         nums[a] += 1  # 对重复元素计数     output = []     i = 0  # 从0开始遍历（从最小值开始遍历）     while len(output) < k:         if nums[i] >= 1:  # 如果该索引处的值大于1，则说明该值存在至少1次，循环往output里面写             for j in range(nums[i]):                 output.append(i)         i += 1     return output[:k]  # 一定要注意单个重复的元素多余k个的情况 

讯享网60+专家，13个技术领域，CSDN 《IT 人才成长路线图》重磅来袭！直接扫码或微信搜索「CSDN」公众号，后台回复关键词「路线图」，即可获取完整路线图！ ☞“时隔 10 年，重新开始写代码的我要崩溃了！”☞Linux 30 年专访：Linus Torvalds 谈 Linux 内核开发与 Git☞Google 宣布 Kotlin-first 已四年，为什么 Java 开发者仍不买账？