一道头条算法题，一种不为人知的解法！

作者丨小夕

来源丨小夕学算法（ID：gh_a73f3afde197）

题目

输入整数数组 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个的情况

识别关注我们

了解更多精彩内容

点分享

点点赞

点在看