首页 > 图灵资讯 > java面试题>正文
1 亿个数据取出最大前 100 个有什么方法
2024-06-19 13:24:02
要从1亿个数据中找出最大的前100个，通常可以使用堆（Heap）数据结构来实现，特别是最小堆（Min Heap）。
以下是一种常见的方法：
1.创建一个最小堆，并将前100个数据插入堆中。
2.遍历剩余的数据，对于每个数据，如果它比堆顶的元素大，就将堆顶元素弹出，然后将当前数据插入堆中。
3.继续遍历所有数据，不断地维护堆，确保堆中保留的是最大的100个数据。
4.当遍历完成后，堆中的元素就是前100个最大的数据。
这种方法的时间复杂度是O(N * log(100))，其中N是数据总数，因为在堆中保持了100个元素。这比将所有数据排序的时间复杂度要低得多。
在Java中，你可以使用PriorityQueue（优先队列）来实现最小堆，PriorityQueue默认是最小堆，因此可以很方便地解决这个问题。以下是一个示例代码：
import java.util.PriorityQueue;
public class Top100LargestNumbers {
public static int[] findTop100LargestNumbers(int[] nums) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(100);
for (int num : nums) {
if (minHeap.size() < 100) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
int[] result = new int[100];
for (int i = 0; i < 100; i++) {
result[i] = minHeap.poll();
}
return result;
}
public static void main(string[] args) {
int[] nums = { /* 1亿个数据 */ };
int[] top100 = findTop100LargestNumbers(nums);
for (int num : top100) {
System.out.println(num);
}
}
}
这段代码中，我们使用PriorityQueue来维护最小堆，然后遍历1亿个数据，将前100个最大的数据保存在堆中。最后，我们将堆中的元素取出，就得到了前100个最大的数据。