486 · 合并k个排序数组

两两合并

  1. public int[] mergekSortedArrays(int[][] arrays) {
  2.        if(arrays == null || arrays.length == 0) return null;
  3.        return merge(arrays, 0, arrays.length - 1);
  4.     }
  5. public int[] merge(int[][] arrays, int l, int r){
  6.         if(l == r) return arrays[l];
  7.         if(l + 1 == r) return mergeTwo(arrays[l], arrays[r]);
  9.         int mid = l + r >> 1;
  10.         int[] left = merge(arrays, l , mid);
  11.         int[] right = merge(arrays, mid + 1, r);
  12.         return mergeTwo(left, right);
  13.     }
  1. public class Solution {
  2.     /**
  3.      * @param arrays: k sorted integer arrays
  4.      * @return: a sorted array
  5.      */
  6.     public int[] mergekSortedArrays(int[][] arrays) {
  7.        if(arrays == null || arrays.length == 0) return null;
  8.        return merge(arrays, 0, arrays.length - 1);
  9.     }
  10.     public int[] merge(int[][] arrays, int l, int r){
  11.         if(l == r) return arrays[l];
  12.         if(l + 1 == r) return mergeTwo(arrays[l], arrays[r]);
  14.         int mid = l + r >> 1;
  15.         int[] left = merge(arrays, l , mid);
  16.         int[] right = merge(arrays, mid + 1, r);
  17.         return mergeTwo(left, right);
  18.     }
  19.     public int[] mergeTwo(int[] a, int[] b){
  20.         int[] c = new int[a.length + b.length];
  21.         int i = 0, j = 0, t = 0;
  22.         while(i < a.length && j < b.length){
  23.             if(a[i] <= b[j]){
  24.                 c[t++] = a[i++];
  25.             }else{
  26.                 c[t++] = b[j++];
  27.             }
  28.         }
  29.         while(i < a.length) c[t++] = a[i++];
  30.         while(j < b.length) c[t++] = b[j++];
  31.         return c;
  32.     }
  33. }

堆

别人写的

class Element {
    public int row, col, val;
    public Element(int row, int col, int val) {
        this.row = row;
        this.col = col;
        this.val = val;
    }
}

public class Solution {
    /**
     * @param arrays: k sorted integer arrays
     * @return: a sorted array
     */
    public int[] mergekSortedArrays(int[][] arrays) {
        // write your code here
        // min-heap O(Nlogk)
        Comparator<Element> cmp = new Comparator<Element>() {
            @Override
            public int compare(Element e1, Element e2) {
                return e1.val - e2.val;
            }
        };

        int k = arrays.length;
        PriorityQueue<Element> pq = new PriorityQueue<>(k, cmp);

        int size = 0;
        for(int i = 0; i < k; i++) {
            if(arrays[i].length > 0) {
                Element e = new Element(i, 0, arrays[i][0]);
                pq.offer(e);
                size += arrays[i].length;
            }
        }

        int[] ans = new int[size];
        int index = 0;
        while(!pq.isEmpty()) {
            Element tmp = pq.poll();
            ans[index++] = tmp.val;

            int next_row = tmp.row, next_col = tmp.col + 1;
            if(next_row < arrays.length && next_col < arrays[next_row].length) {
                Element next = new Element(next_row, next_col, arrays[next_row][next_col]);
                pq.offer(next);
            }
        }
        return ans;
    }
}

23. 合并K个升序链表

两两合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r){
        if(l == r) return lists[l];
        if(l + 1 == r) return mergeTwo(lists[l], lists[r]);
        int mid = l + r >> 1;
        ListNode lnode = merge(lists, l, mid);
        ListNode rnode = merge(lists, mid + 1, r);
        return mergeTwo(lnode, rnode);
    }
    public ListNode mergeTwo(ListNode a, ListNode b){
        if(a == null) return b;
        if(b == null) return a;
        if(a.val <= b.val) {
            a.next = mergeTwo(a.next, b);
            return a;
        }else{
            b.next = mergeTwo(a, b.next);
            return b;
        }
    }
}

堆

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        for(ListNode node : lists){
            if(node != null) pq.offer(node);
        }
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null) pq.offer(node.next);
        }
        return dummy.next;
    }
}