最小的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. }