有1000个有序的数组,每个数组至少有一个元素,找出最大的10个元素,用Java代码实现
时间: 2024-05-15 12:17:41 浏览: 117
可以使用堆排序来实现:
```
import java.util.PriorityQueue;
public class Solution {
public static void main(String[] args) {
int[][] arrays = {{1,2,5,7,9}, {2,4,6,8}, {1,3,5,7,9}, {2,4,6,8}, {1,11,21}, {3,4,6,7,10,14}, {17,20,23}, {6,7,9,10,12,13}, {0,1,3,5}, {7,8,11,15}};
int k = 10;
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
for(int i = 0; i < arrays.length; i++) {
int[] array = arrays[i];
for(int j = 0; j < array.length; j++) {
int num = array[j];
if(minHeap.size() < k) {
minHeap.offer(num);
} else if(num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
}
System.out.println(minHeap);
}
}
```
将所有数组中的元素遍历并添加到一个大小为k的最小堆中,最终最小堆中的元素就是最大的10个元素。时间复杂度为O(n*k*logk),n为数组个数,k为最大元素数目。如果n比较小,k比较大,可以使用快速排序或归并排序来优化时间复杂度。
阅读全文