10 亿数，找最大 100 个

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

思路：

1.  **使用最小堆（Min Heap）** ：维护一个包含100个元素的最小堆。开始时，将前100个数添加到最小堆中。然后，对于剩余的数字，如果它比最小堆中的最小值大，就将它添加到最小堆中，并且移除最小堆中的最小值。这样，最小堆中始终保持了最大的100个数。
2.  **遍历10亿个数字**：依次遍历10亿个数字，如果当前数字比最小堆的最小值大，就将它添加到最小堆中，然后移除最小堆中的最小值。
3.  **最小堆中的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);
        }
    }

当然还有其他思路：

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