- 首页 > it技术 > >
2000个数组，每个200大小，数组内有序，求所有数组的TOP1000
import java.util.Arrays;
/**
* 2000个数组，每个200大小，数组内有序，求所有数值的TOP1000
* @author dell
*
*/
public class PrintMaxTop { public static class HeapNode {
public int value;
public int arrNum;
public int index;
public HeapNode(int value, int arrNum, int index) {
this.value = https://www.it610.com/article/value;
this.arrNum = arrNum;
this.index = index;
}
} public static void printTopK(int[][] matrix, int topK) {
int heapSize = topK;
HeapNode[] heap = new HeapNode[heapSize];
for (int i = 0;
i != heapSize;
i++) {
int index = matrix[i].length - 1;
heap[i] = new HeapNode(matrix[i][index], i, index);
heapInsert(heap, i);
}System.out.println("TOP " + topK + " : ");
for (int i = 0;
i != topK;
i++) {if (heapSize == 0) {
break;
}
System.out.println(heap[i].value + " ");
} } public static void heapInsert(HeapNode[] heap, int index) {while (index != 0) {int parent=index-1;
if (heap[parent].value< heap[index].value) {
swap(heap, parent, index);
index = parent;
} else {
break;
}} } public static void heapify(HeapNode[] heap, int index, int heapSize) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
while (left < heapSize) {
if (heap[left].value > heap[index].value) {
largest = left;
}
if (right < heapSize && heap[right].value > heap[largest].value) {
largest = right;
}
if (largest != index) {
swap(heap, largest, index);
} else {
break;
}
index = largest;
left = index * 2 + 1;
right = index * 2 + 2;
}
}
public static void swap(HeapNode[] heap, int index1, int index2) {
HeapNode tmp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = tmp;
} public static int[][] generateRandomMatrix(int row, int col,int maxValue) {
if (row < 0 || col < 0) {
return null;
}
int[][] matrix = new int[row][col];
for (int i = 0;
i != matrix.length;
i++) {
for (int j = 0;
j != matrix[i].length;
j++) {
matrix[i][j] = (int) (Math.random() * maxValue);
}
Arrays.sort(matrix[i]);
}return matrix;
} public static void printMatrix(int[][] matrix) {
for (int i = 0;
i != matrix.length;
i++) {
for (int j = 0;
j != matrix[i].length;
j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
} } public static void main(String[] args) {int[][] matrix = generateRandomMatrix(2000, 200, 1000);
printMatrix(matrix);
System.out.println("===========================");
printTopK(matrix, 1000);
}}
推荐阅读
