1. import lombok.Data;
    3. import java.util.Arrays;
    4. import java.util.PriorityQueue;
    6. /**
    8. @author  https://github.com/yanglbme
    9. */
    10. @Data  
    11. public class DataWithSource implements Comparable {
    12.     /** 
    13.     数值
    14.     */
    15.     private int value;
    16.     /** 
    17.     记录数值来源的数组
    18.     */
    19.     private int source;
    20.     /** 
    21.     记录数值在数组中的索引
    22.     */
    23.     private int index;
    24.     public DataWithSource(int value, int source, int index) {
    25.         this.value = value;
    26.         this.source = source;
    27.         this.index = index;
    28.     }
    29.     /**
    30.     * 
    31.     由于 PriorityQueue 使用小顶堆来实现，这里通过修改
    32.     两个整数的比较逻辑来让 PriorityQueue 变成大顶堆
    33.     */
    34.     @Override  
    35.     public int compareTo(DataWithSource o) {
    36.         return Integer.compare(o.getValue(), this.value);
    37.     }
    38. }
    40. class Test {
    41.     public static int[] getTop(int[][] data) {
    42.         int rowSize = data.length;
    43.         int columnSize = data[0].length;
    44.         // 创建一个columnSize大小的数组，存放结果
    45.         int[] result = new int[columnSize];
    47.         PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
    48.         for (int i = 0; i < rowSize; ++i) {
    49.             // 将每个数组的最大一个元素放入堆中
    50.             DataWithSource d = new DataWithSource(data[i][0], i, 0);
    51.             maxHeap.add(d);
    52.         }
    54.         int num = 0;
    55.         while (num < columnSize) {
    56.             // 删除堆顶元素
    57.             DataWithSource d = maxHeap.poll();
    58.             result[num++] = d.getValue();
    59.             if (num >= columnSize) {
    60.                 break;
    61.             }
    63.             d.setValue(data[d.getSource()][d.getIndex() + 1]);
    64.             d.setIndex(d.getIndex() + 1);
    65.             maxHeap.add(d);
    66.         }
    67.         return result;
    69.     }
    71.     public static void main(String[] args) {
    72.         int[][] data = {
    73.             {29, 17, 14, 2, 1},
    74.             {19, 17, 16, 15, 6},
    75.             {30, 25, 20, 14, 5},
    76.         };
    78.         int[] top = getTop(data);
    79.         System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
    80. }

    }