• 最小的K个数
    • 题目
    • 解题思路

    最小的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. }
    6. for (int i = input.length - 1; i >= 0; i--) {
    7. minHeap(input, 0, i);
    8. swap(input, 0, i);
    9. res.add(input[i]);
    10. if (res.size() == k) break;
    11. }
    12. return res;
    13. }
    14. private void minHeap(int[] heap, int start, int end) {
    15. if (start == end) {
    16. return;
    17. }
    18. int childLeft = start * 2 + 1;
    19. int childRight = childLeft + 1;
    20. if (childLeft <= end) {
    21. minHeap(heap, childLeft, end);
    22. if (heap[childLeft] < heap[start]) {
    23. swap(heap, start, childLeft);
    24. }
    25. }
    26. if (childRight <= end) {
    27. minHeap(heap, childRight, end);
    28. if (heap[childRight] < heap[start]) {
    29. swap(heap, start, childRight);
    30. }
    31. }
    32. }
    33. private void swap(int[] nums, int a, int b) {
    34. int t = nums[a];
    35. nums[a] = nums[b];
    36. nums[b] = t;
    37. }