题解 | #最小的K个数#

package com.hhdd;

import java.util.ArrayList;

/**
 * @Author huanghedidi
 * @Date 2024/3/20 21:36
 */
public class 最小的K个数 {
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        // write code here
        if (k == 0) {
            return new ArrayList<Integer>();
        }
        makeHeap(input);
        ArrayList<Integer> res = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            res.add(input[0]);
            // 交换顺序，然后调整堆
            int tmp = input[0];
            input[0] = input[input.length - 1 - i];
            input[input.length - 1 - i] = tmp;
            adjust(input, input.length - 1 - i - 1);
        }
        return res;
    }

    // 成堆
    public static void makeHeap(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int cur = i;
            while (input[cur] < input[(cur - 1) / 2]) {
                int tmp = input[cur];
                input[cur] = input[(cur - 1) / 2];
                input[(cur - 1) / 2] = tmp;
                cur = (cur - 1) / 2;
            }
        }
    }

    public static void adjust(int[] input, int end) {
        int cur = 0;
        while (cur <= end) {
            int left = cur * 2 + 1;
            int smallest = cur;
            if (left <= end) {
                smallest = input[cur] > input[left] ? left : cur;
                int right = left + 1;
                if (right <= end) {
                    smallest = input[smallest] > input[right] ? right : smallest;
                }
            }
            if (smallest == cur) {
                break;
            }
            int tmp = input[cur];
            input[cur] = input[smallest];
            input[smallest] = tmp;
            cur = smallest;
        }
    }

    public static void main(String[] args) {
        int[] input = new int[]{0, 1, 1, 1, 4, 5, 3, 7, 7, 8, 10, 2, 7, 8, 0, 5, 2, 16, 12, 1, 19, 15, 5, 18, 2, 2, 22, 15, 8, 22, 17, 6, 22, 6, 22, 26, 32, 8, 10, 11, 2, 26, 9, 12, 9, 7, 28, 33, 20, 7, 2, 17, 44, 3, 52, 27, 2, 23, 19, 56, 56, 58, 36, 31, 1, 19, 19, 6, 65, 49, 27, 63, 29, 1, 69, 47, 56, 61, 40, 43, 10, 71, 60, 66, 42, 44, 10, 12, 83, 69, 73, 2, 65, 93, 92, 47, 35, 39, 13, 75};
        ArrayList<Integer> res = GetLeastNumbers_Solution(input, 75);
        System.out.println(res);
    }

}