本题为剑指offer面试题30
牛客网测试地址：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf
[编程题]最小的K个数 热度指数：88997 时间限制：1秒 空间限制：32768K算法知识视频讲解 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
代码如下：
package go.jacob.day506; import java.util.ArrayList; import java.util.Stack; /** * @author Administrator * 用最小堆实现 * 思路：建立一个最大堆，堆大小为k。当堆不满时，直接插入元素； * 当堆满，将插入元素k与堆中最大元素max比较，如果k<max,将max替换为k，否则不操作。 */ public class Demo2 { ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) { //鲁棒性判断 if (input == null || k <= 0 || k > input.length) return list; MaxPQ q = new MaxPQ(k); //最小堆插入元素O(log(n)) for (int i = 0; i < input.length; i++) { q.insert(input[i]); } //用堆栈堆元素进行反序 Stack<Integer> stack = new Stack<Integer>(); while (q.size > 0) { stack.push(q.delMax()); } while (!stack.isEmpty()) { list.add(stack.pop()); } return list; } } /* * 最大堆 */ class MaxPQ { int[] arr = null; int size = 0; int maxNum = 0; //数组下标从1开始 public MaxPQ(int maxNum) { arr = new int[maxNum + 1]; this.maxNum = maxNum; } //删除最大元素 public int delMax() { if (size <= 0) throw new RuntimeException("堆空"); if (size == 1) { size--; return arr[1]; } int max = arr[1]; arr[1] = arr[size--]; sink(1); return max; } //插入元素 public void insert(int v) { if (size < maxNum) { arr[++size] = v; swim(size); } else { if (arr[1] > v) { arr[1] = v; sink(1); } } } //下沉 private void sink(int k) { while (k * 2 <= size) { int child = k * 2; if (child < size) { if (arr[child] < arr[child + 1]) child++; } if (arr[k] < arr[child]) { exch(arr, k, child); k = child; } else break; } } //上浮 private void swim(int k) { arr[0] = arr[k]; while (arr[k] > arr[k / 2]) { exch(arr, k, k / 2); k = k / 2; } } private void exch(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }