1. 题目
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
2. 示例
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
3. 提示
-
0 <= len(arr) <= 100000 -
0 <= k <= min(100000, len(arr))
4. 题解
本题有两种方式实现
1、排序：最小到最大排序，然后取钱k个，时间复杂度O(nlogn)、空间复杂度O(logn)
2、堆：因为最大堆实时维护数组的前K小值。首先将前k个数插入大根堆，然后从K+1个数开始遍历，比较堆顶元素与第k+1个数。若小，不变；若大，先出堆顶元素放入第k+1元素。时间复杂度O(nlogk)、空间复杂度O(k)。
5. Code
1 public int[] smallestKA(int[] arr, int k) {
2 /**
3 * @Method: smallestKA
4 * @Author: haifwu
5 * @Version: 1.0
6 * @Date: 28/05/2021 12:05
7 * @param arr
8 * @param k
9 * @Return: int[]
10 * @Description: 排序（暴力）
11 * 最小到最大排序，然后取前k个
12 * 时间复杂度O(nlogn)
13 * 空间复杂度（logn）
14 */
15 if(arr.length == k) {
16 return arr;
17 }
18 Arrays.sort(arr);
19 int[] temp = new int[k];
20 for(int i = 0; i < k; i++) {
21 temp[i] = arr[i];
22 }
23 return temp;
24 }
1 public int[] smallestKB(int[] arr, int k) {
2 /**
3 * @Method: smallestKB
4 * @Author: haifwu
5 * @Version: 1.0
6 * @Date: 28/05/2021 12:07
7 * @param arr
8 * @param k
9 * @Return: int[]
10 * @Description: 堆
11 * 因为大根堆实时维护数组的前k小值。
12 * 首先将前k个数插入大根堆，
13 * 然后从K+1个数开始遍历，
14 * 比较堆顶元素与第k+1个数，
15 * 若小，不变
16 * 若大，先出堆顶元素放入。
17 * 时间复杂度：O(nlongk)
18 * 空间复杂度：O(k)
19 */
20 int[] temp = new int[k];
21 if(k == 0) {
22 return temp;
23 }
24 if(arr.length == k) {
25 return arr;
26 }
27 PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
28 @Override
29 public int compare(Integer integer, Integer t1) {
30 return t1 - integer;
31 }
32 });
33 for(int i = 0; i < k; i++) {
34 queue.offer(arr[i]);
35 }
36 for(int i = k; i < arr.length; i++) {
37 if(queue.peek() > arr[i]) {
38 queue.poll();
39 queue.offer(arr[i]);
40 }
41 }
42 for(int i = 0; i < k; i++) {
43 temp[i] = queue.poll();
44 }
45 return temp;
46 }