小学生都能看懂的题解 | #最小的K个数#

方案解释

假设你有一堆球（代表数字），你想找出其中最小的几个球（代表数字）。怎么做呢？

1. 准备工具：你需要一个篮子（相当于最大堆），用来装这些球。
2. 装球：先往篮子里放几个球（最小的 k 个球）。
3. 换球：如果你发现地上还有更小的球，就把篮子里最大的球拿出来，换上那个更小的球。
4. 继续换球：一直这样做，直到所有的球都看过一遍。
5. 完成：最后篮子里的球就是最小的那些球。

代码实现

让我们把这些步骤变成 Java 代码。我们会用一个叫做 PriorityQueue 的工具来实现我们的“篮子”。

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {
    /**
     * 找出数组中最小的 k 个数
     * @param input 输入数组
     * @param k 要找出的最小数的数量
     * @return 不去重的最小的 k 个数
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        // 如果输入的数据有问题，直接返回一个空列表
        if (input == null || input.length == 0 || k <= 0 || k > input.length) {
            return new ArrayList<>();
        }

        // 创建一个“篮子”（最大堆）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);

        // 先往篮子里放 k 个球
        for (int i = 0; i < k; i++) {
            maxHeap.offer(input[i]);
        }

        // 继续看其他的球
        for (int i = k; i < input.length; i++) {
            // 如果发现更小的球，就把篮子里最大的球拿出来，换上这个球
            if (input[i] < maxHeap.peek()) {
                maxHeap.poll(); // 拿出篮子里最大的球
                maxHeap.offer(input[i]); // 放进更小的球
            }
        }

        // 最后篮子里的球就是我们要找的最小的 k 个数
        ArrayList<Integer> result = new ArrayList<>(maxHeap);
        return result;
    }
}

代码解释

1. 初始化：
1. 首先检查输入是否有效，如果不合法就直接返回空列表。
2. 创建篮子：
1. 创建一个 PriorityQueue（篮子），用来存储最小的 k 个数。
2. 为了让这个篮子变成最大堆，我们使用自定义的比较器 (a, b) -> b - a。
3. 装球：
1. 将数组中的前 k 个数放进篮子里。
4. 换球：
1. 遍历数组中的其他数，如果发现有更小的数，就拿出篮子里最大的数，换成这个更小的数。
5. 完成：
1. 遍历完成后，篮子里的数就是最小的 k 个数。

示例

假设我们有一个数组 [4, 5, 1, 6, 2, 7, 3, 8]，我们要找出最小的 4 个数。

1. 初始化篮子：
1. 先放 [4, 5, 1, 6] 进去。
2. 换球：
1. 第 5 个数是 2，比篮子里最大的 6 小，所以拿出 6，放进 2。
2. 第 6 个数是 7，不比篮子里的任何数小，所以不换。
3. 第 7 个数是 3，比篮子里最大的 5 小，所以拿出 5，放进 3。
4. 第 8 个数是 8，不比篮子里的任何数小，所以不换。
3. 完成：
1. 最后篮子里的数是 [1, 2, 3, 4]。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。