题目描述：
输入整数数组 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
第一时间想到的就是利用Arrays.sort来对数组排序，然后将其复制给另外一个数组，最后返回就可以了，不过这样的运行效率并不高
class Solution { public int[] getLeastNumbers(int[] arr, int k) { Arrays.sort(arr); int []array = new int[k]; for(int i = 0;i < k;i++){ array[i] = arr[i]; } return array; } }
换一种方式，用计数排序解决TopK问题：O(N)
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; } }
运行效率：
