要从1亿个数据中找出最大的前100个,通常可以使用堆(Heap)数据结构来实现,特别是最小堆(Min Heap)。
以下是一种常见的方法:
1创建一个最小堆,并将前100个数据插入堆中。
2遍历剩余的数据,对于每个数据,如果它比堆顶的元素大,就将堆顶元素弹出,然后将当前数据插入堆中。
3继续遍历所有数据,不断地维护堆,确保堆中保留的是最大的100个数据。
4当遍历完成后,堆中的元素就是前100个最大的数据。
这种方法的时间复杂度是O(N * log(100)),其中N是数据总数,因为在堆中保持了100个元素。这比将所有数据排序的时间复杂度要低得多。
在Java中,你可以使用PriorityQueue(优先队列)来实现最小堆,PriorityQueue默认是最小堆,因此可以很方便地解决这个问题。以下是一个示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
|
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个最大的数据。