当前位置: 首页 > 图灵资讯 > java面试题> 1 亿个数据取出最大前 100 个有什么方法

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个最大的数据。