问题来自牛客剑指offer

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

问题思路

利用排序：最直观的我觉得就是选择排序，因为选择排序是按照每次固定一个数的思路来的，我们将外层控制排列轮数的值改为K即可。利用堆结构（巧妙）利用堆（java中的PriorityQueue）先存储K个元素，形成一个大根堆。之后每次新来的数都和堆顶比较，如果大于堆顶：那么这个数一定不是前K个最小的数，如果小于堆顶，就把堆顶的数弹出，并把新的数压入。一次遍历完整个数组就可以得到前K个最小的数。

Code

//选择法 public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) { ArrayList<Integer> array = new ArrayList(); if (k > input.length) return array; for (int i = 0; i < k; i++) { int min = i; for (int j = i; j < input.length; j++) { if (input[j] < input[min]) min = j; } int temp = input[i]; input[i] = input[min]; input[min] = temp; array.add(input[i]); } return array; } //利用大根堆 public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) { ArrayList<Integer> array = new ArrayList(); if (input.length < k || input.length == 0 || k == 0) return array; /** * private void siftUpUsingComparator(int k, E x) { * while (k > 0) { * int parent = (k - 1) >>> 1; * Object e = queue[parent]; * if (comparator.compare(x, (E) e) >= 0) * break; * queue[k] = e; * k = parent; * } * queue[k] = x; * } * 以上为PriorityQueue添加对象时比较器的使用，可以看到，当x（父）比e（当前的节点）要大，那么就break，不进行交换，所以如果 * 要形成大根堆，则需要将比较规则设置为 o2-o1 */ //实际上和数组存储没有什么区别，底层仍然是建立了数组，就和二叉树的数组存储的规则是一样的 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); // 放入k个数 for (int i = 0; i < k; i++) { //底层调用offer方法 priorityQueue.add(input[i]); } // 开始比较 for (int i = k; i < input.length; i++) { if (priorityQueue.peek() < input[i]) continue; else { priorityQueue.poll(); priorityQueue.add(input[i]); } } for (Integer item : priorityQueue) { array.add(item); } return array; }