10 亿数，找最大 100 个-蒲公英云

10 亿数，找最大 100 个

亦凉 2024-02-21 10:57 133阅读 0赞

思路：

使用最小堆（Min Heap） ：维护一个包含100个元素的最小堆。开始时，将前100个数添加到最小堆中。然后，对于剩余的数字，如果它比最小堆中的最小值大，就将它添加到最小堆中，并且移除最小堆中的最小值。这样，最小堆中始终保持了最大的100个数。
遍历10亿个数字：依次遍历10亿个数字，如果当前数字比最小堆的最小值大，就将它添加到最小堆中，然后移除最小堆中的最小值。
最小堆中的100个数就是最大的100个数：当遍历完10亿个数字后，最小堆中的100个数将是最大的100个数。

实现上述思路：

import java.util.PriorityQueue;
public class Top100LargestNumbers {
    public static void findTop100LargestNumbers(int[] numbers) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(100);
        // 初始化最小堆
        for (int i = 0; i < 100; i++) {
            minHeap.add(numbers[i]);
        }
        // 处理剩余的数字
        for (int i = 100; i < numbers.length; i++) {
            int num = numbers[i];
            if (num > minHeap.peek()) {
                minHeap.poll(); // 移除最小值
                minHeap.add(num);
            }
        }
        // 打印最大的100个数
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
    }
    public static void main(String[] args) {
        int[] numbers = {
     /* 10亿个数字 */ };
        findTop100LargestNumbers(numbers);
    }
}

当然还有其他思路：

分布式计算：如果处理的数据量非常大，可以考虑使用分布式计算框架，如Apache Hadoop或Apache Spark。这些框架可以将任务分布到多台计算机上，以处理大规模数据并找到最大的100个数。
MapReduce：使用MapReduce模型，将数据分成小块，然后在多个计算节点上并行处理它们。在不同的节点上查找最大的数，然后将结果合并以找到整体的最大100个数。
分区和排序：将10亿个数字分成多个分区，并在每个分区内进行排序。然后，选择每个分区的前100个数，并在这些候选数中找到最大的100个。
采样和分区：对数据进行随机采样，以获取大致的数据分布。然后将数据分成多个分区，并在每个分区内找到最大的100个数。最后，从这些部分结果中找到最大的100个。
外部排序：将数据划分为多个块，然后对每个块进行外部排序。接着，使用归并排序的方法来合并排序后的块，并找到全局最大的100个数。
数据库管理系统：如果数据存储在数据库中，可以使用SQL查询来找到最大的100个数，使用ORDER BY和LIMIT子句。