最小的K个数

题目

牛客网

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

解题思路

  1. 利用堆排序原理，计算出最小的 k 个数
  1. public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
  2.     ArrayList<Integer> res = new ArrayList<>();
  3.     if (k > input.length || k == 0) {
  4.         return res;
  5.     }
  7.     for (int i = input.length - 1; i >= 0; i--) {
  8.         minHeap(input, 0, i);
  10.         swap(input, 0, i);
  12.         res.add(input[i]);
  13.         if (res.size() == k) break;
  14.     }
  15.     return res;
  16. }
  18. private void minHeap(int[] heap, int start, int end) {
  19.     if (start == end) {
  20.         return;
  21.     }
  23.     int childLeft = start * 2 + 1;
  24.     int childRight = childLeft + 1;
  26.     if (childLeft <= end) {
  27.         minHeap(heap, childLeft, end);
  29.         if (heap[childLeft] < heap[start]) {
  30.             swap(heap, start, childLeft);
  31.         }
  32.     }
  34.     if (childRight <= end) {
  35.         minHeap(heap, childRight, end);
  37.         if (heap[childRight] < heap[start]) {
  38.             swap(heap, start, childRight);
  39.         }
  40.     }
  41. }
  43. private void swap(int[] nums, int a, int b) {
  44.     int t = nums[a];
  45.     nums[a] = nums[b];
  46.     nums[b] = t;
  47. }