如何通过1亿个整数里找出最大的前100个整数？

在 **1 亿个整数** 中找到 **最大的前 100 个数**，可以使用以下高效方法： ## **1. 小顶堆（优先队列，推荐）** ### **思路** 使用 **小顶堆（Min Heap）** 维护前 100 个最大的数： - **优先队列（PriorityQueue）** 维护 100 个元素，堆顶是最小的元素。 - **遍历 1 亿个数**，如果当前数比堆顶大，则替换并调整堆。 ### **时间复杂度** - 插入堆的时间复杂度：`O(log 100) ≈ O(7)` - 处理 1 亿个数的时间复杂度：`O(10^8 * log 100) ≈ O(10^8)` ### **代码示例** ```java import java.util.PriorityQueue; import java.util.Random; public class Top100MaxNumbers { public static void main(String[] args) { int n = 100000000; // 1亿个整数 int topK = 100; // 需要找的前100个最大值 Random random = new Random(); // 小顶堆（默认是最小堆） PriorityQueue<Integer> minHeap = new PriorityQueue<>(topK); for (int i = 0; i < n; i++) { int num = random.nextInt(Integer.MAX_VALUE); // 生成随机数 if (minHeap.size() < topK) { minHeap.offer(num); } else if (num > minHeap.peek()) { minHeap.poll(); // 移除最小值 minHeap.offer(num); } } // 输出结果 System.out.println("Top 100 max numbers:"); while (!minHeap.isEmpty()) { System.out.println(minHeap.poll()); } } } ``` ## **2. 快速选择算法（QuickSelect，适用于小数据）** ### **思路** - **类似快速排序**，但只递归到第 `n-100` 个元素，不需要完整排序。 - **时间复杂度**：`O(N)`，最坏情况 `O(N^2)` ### **代码** ```java import java.util.Random; public class QuickSelectTop100 { public static void main(String[] args) { int n = 100000000; int topK = 100; int[] arr = new Random().ints(n, 0, Integer.MAX_VALUE).toArray(); int index = partition(arr, 0, arr.length - 1, arr.length - topK); int[] top100 = new int[topK]; System.arraycopy(arr, index, top100, 0, topK); System.out.println("Top 100 max numbers:"); for (int num : top100) { System.out.println(num); } } private static int partition(int[] arr, int left, int right, int k) { if (left == right) return left; int pivotIndex = left + new Random().nextInt(right - left + 1); int pivot = arr[pivotIndex]; int storeIndex = left; swap(arr, pivotIndex, right); for (int i = left; i < right; i++) { if (arr[i] < pivot) swap(arr, storeIndex++, i); } swap(arr, storeIndex, right); if (storeIndex == k) return storeIndex; else if (storeIndex < k) return partition(arr, storeIndex + 1, right, k); else return partition(arr, left, storeIndex - 1, k); } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ``` ## **3. 外部排序（适用于数据太大，内存不足的情况）** 如果 **数据无法全部放入内存**，可以使用 **外部排序**： 1. **分块读取（Chunking）**：将 1 亿个数分为多个小文件，每个文件 **使用小顶堆选出 100 个最大数**。 2. **归并排序（Merge Sort）**：合并多个小文件中的最大数，最终选出 100 个最大数。 ### **思路** - 设每个块 **包含 100 万个数**，分成 `100` 个块，每个块独立选出 **100 个最大值**（`O(n log 100)`）。 - 最终合并 `100` 个块中的 **100 * 100 = 10000 个数**，再用小顶堆选出最终 **100 个最大值**。 ### **代码示例** ```java import java.io.*; import java.util.PriorityQueue; import java.util.Scanner; public class ExternalSortTop100 { private static final int CHUNK_SIZE = 1000000; // 100万一块 public static void main(String[] args) throws IOException { String inputFile = "bigdata.txt"; // 假设存储1亿个整数 String[] chunkFiles = splitIntoChunks(inputFile); // 小顶堆合并各个chunk的前100 PriorityQueue<Integer> minHeap = new PriorityQueue<>(100); for (String chunkFile : chunkFiles) { try (Scanner scanner = new Scanner(new File(chunkFile))) { while (scanner.hasNextInt()) { int num = scanner.nextInt(); if (minHeap.size() < 100) { minHeap.offer(num); } else if (num > minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } } } System.out.println("Top 100 max numbers:"); while (!minHeap.isEmpty()) { System.out.println(minHeap.poll()); } } private static String[] splitIntoChunks(String inputFile) throws IOException { BufferedReader reader = new BufferedReader(new FileReader(inputFile)); int chunkIndex = 0; String line; while ((line = reader.readLine()) != null) { // 分块写入文件 int[] numbers = new int[CHUNK_SIZE]; int i = 0; do { numbers[i++] = Integer.parseInt(line); } while (i < CHUNK_SIZE && (line = reader.readLine()) != null); // 选出当前块的前100个最大值 PriorityQueue<Integer> minHeap = new PriorityQueue<>(100); for (int num : numbers) { if (minHeap.size() < 100) { minHeap.offer(num); } else if (num > minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } // 写入临时文件 try (BufferedWriter writer = new BufferedWriter(new FileWriter("chunk_" + chunkIndex + ".txt"))) { while (!minHeap.isEmpty()) { writer.write(minHeap.poll() + "\n"); } } chunkIndex++; } return new File(".").list((dir, name) -> name.startsWith("chunk_")); } } ``` ## **总结** | 方法 | 适用场景 | 时间复杂度 | 适用数据规模 | |------|---------|---------|-------------| | **小顶堆（优先队列）** | **内存足够，数据量大** | **O(N log K)** | **10^8 级别** | | **快速选择（QuickSelect）** | **数据较小（如 10^6 级别）** | **O(N) 最坏 O(N²)** | **10^6 级别** | | **外部排序（External Sort）** | **数据超大（无法全部加载）** | **O(N log K)** | **10^9 级别** | **推荐方案**： - **内存足够** → **小顶堆** - **数据较小（百万级）** → **快速选择** - **数据太大（超过内存）** → **外部排序** 对于 **1 亿个整数**，**小顶堆（优先队列）是最优选择**，可以高效求出前 100 个最大数。