1 億個數據取出最大前 100 個有什么方法？

大家好，這是一道經常在面試中被遇到的一個問題，我之前面試也是被問到過得，現在一起學習下，下次再被問到就可以輕松地用對。

在計算機科學和數據處理領域，我們經常會遇到需要從海量的數據中找出最大或最小的若干個元素的情況。本文將以 Java 為例，介紹幾種從 1 億個數據中取出最大前 100 個的方法。

方法一：排序后取前 100 個

最直觀的方法是先將這 1 億個數據排序，然后取排序后的前 100 個。在 Java 中，可以使用 Arrays 類的 sort 方法或者 PriorityQueue 類來實現。

1. 示例：使用 Arrays.sort()

import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] data = generateData(100000000);Arrays.sort(data);int[] top100 = new int[100];System.arraycopy(data, 0, top100, 0, 100);// 輸出最大前 100 個數for (int num : top100) {System.out.print(num + " ");}}public static int[] generateData(int size) {int[] data = new int[size];for (int i = 0; i < size; i++) {data[i] = (int) (Math.random() * 100000000);}return data;}
}

2. 示例：使用 PriorityQueue

import java.util.PriorityQueue;
public class Main {public static void main(String[] args) {int[] data = generateData(100000000);PriorityQueue<Integer> pq = new PriorityQueue<>(100000000, (a, b) -> b - a);for (int num : data) {pq.offer(num);if (pq.size() > 100) {pq.poll();}}int[] top100 = new int[100];while (!pq.isEmpty()) {top100[pq.size() - 1] = pq.poll();}// 輸出最大前 100 個數for (int num : top100) {System.out.print(num + " ");}}public static int[] generateData(int size) {int[] data = new int[size];for (int i = 0; i < size; i++) {data[i] = (int) (Math.random() * 100000000);}return data;}
}

優缺點
? 優點：簡單易懂，代碼實現容易。
? 缺點：時間復雜度較高，對于大數據量來說，排序所需的時間可能會很長。

方法二：使用部分排序算法

部分排序算法（如快速選擇算法）可以在不需要完全排序的情況下找到第 k 大的元素。我們可以使用這個算法來找出最大前 100 個元素。

1. 示例：使用快速選擇算法

import java.util.Random;
public class Main {public static void main(String[] args) {int[] data = generateData(100000000);int[] top100 = findTop100(data);// 輸出最大前 100 個數for (int num : top100) {System.out.print(num + " ");}}public static int[] findTop100(int[] data) {int[] result = new int[100];int left = 0;int right = data.length - 1;for (int i = 0; i < 100; i++) {int pivot = data[(left + right) / 2];int leftCount = 0;int rightCount = data.length - 1 - i;for (int num : data) {if (num > pivot) {rightCount--;} else {leftCount++;}}if (leftCount > rightCount) {right = (left + right) / 2;} else {left = (left + right) / 2 + 1;}result[i] = pivot;}return result;}public static int[] generateData(int size) {int[] data = new int[size];for (int i = 0; i < size; i++) {data[i] = (int) (Math.random() * 100000000);}return data;}
}

優缺點
? 優點：時間復雜度較低，對于大數據量來說，效率更高。
? 缺點：代碼實現相對復雜，需要理解快速選擇算法的原理。 以上就是從 1 億個數據中取出最大前 100 個的幾種方法，各有優缺點，可以根據實際情況選擇合適的方法。

今天的分享就到這里，如果覺得對你有幫助，感謝點贊、分享、關注一波，你的認可是我創造的最大動力。

更多內容請關注公眾號：程序猿漠然，一個分享有趣后端知識的公眾號。