题目
打印N 个数组整体最大的Top K
java代码
package com.lizhouwei.chapter8;
/**
* @Description: 打印N 个数组整体最大的Top K
* @Author: lizhouwei
* @CreateDate: 2018/5/9 20:11
* @Modify by:
* @ModifyDate:
*/
public class Chapter8_20 {
public void printTopK(int[][] matrix, int topK) {
int heapSize = matrix.length;
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.print("TOP" + topK + ": ");
HeapNode node = null;
for (int i = 0; i < topK; i++) {
System.out.print(heap[0].value + " ");
if (heap[0].index != 0) {
heap[0].value = matrix[heap[0].arrNum][--heap[0].index];
} else {
swap(heap, 0, --heapSize);
}
heapify(heap, 0, heapSize);
}
}
public void heapInsert(HeapNode[] heap, int index) {
int parent = 0;
while (index > 0) {
parent = (index - 1) / 2;
if (heap[parent].value < heap[index].value) {
swap(heap, parent, index);
} else {
break;
}
}
}
public void heapify(HeapNode[] heap, int index, int heapSize) {
int left = 2 * index + 1;
int right = 2 * index + 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) {
break;
}
swap(heap, largest, index);
index = largest;
left = 2 * index + 1;
right = 2 * index + 2;
}
}
public void swap(HeapNode[] heap, int a, int b) {
HeapNode temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
}
class HeapNode {
public int value;
public int arrNum;
public int index;
public HeapNode(int value, int arrNum, int index) {
this.value = value;
this.arrNum = arrNum;
this.index = index;
}
//测试
public static void main(String[] args) {
Chapter8_20 chapter = new Chapter8_20();
int[][] arr = {{219, 405, 538, 845, 971}, {148, 558}, {52, 99, 348, 691}};
chapter.printTopK(arr, 5);
}
}
结果
