Merge K sorted array into one big sorted array in ascending order.

Assumptions

  • The input arrayOfArrays is not null, none of the arrays is null either.

注意matrix每一行length可能不等,可能不为0

  public int[] merge(int[][] arrayOfArrays) {
  //注意不能包括第二个条件,因为有可能只是第一行为空
    if (arrayOfArrays.length == 0 /*|| arrayOfArrays[0].length == 0 */) {
      return new int[0];
    }
    int size = 0;
    for (int i = 0; i < arrayOfArrays.length; i++) {
      size += arrayOfArrays[i].length;
    }
    int[] ans = new int[size];
    PriorityQueue<Pair> pq = new PriorityQueue<>(1, new Comparator<Pair>() {
      public int compare(Pair a, Pair b) {
        return a.val - b.val;
      }
    });
    for (int i = 0; i < arrayOfArrays.length; i++) {
      if (arrayOfArrays[i].length > 0) {
        pq.offer(new Pair(arrayOfArrays[i][0], i, 0));
      }
    }
    int index = 0;
    while (!pq.isEmpty()) {
      Pair cur = pq.poll();
      ans[index++] = cur.val;
      if (cur.y + 1 < arrayOfArrays[cur.x].length) {
        pq.offer(new Pair(arrayOfArrays[cur.x][cur.y + 1], cur.x, cur.y + 1));
      }
    }
    return ans;
  }
  class Pair {
    int val, x, y;
    public Pair(int val, int x, int y) {
      this.val = val;
      this.x = x;
      this.y = y;
    }
  }

results matching ""

    No results matching ""