Merge K Sorted Arrays

Array, Heap, Priority Queue

Description

Given _k _sorted integer arrays, merge them into one sorted array.

Example

Example 1:

Input: 
  [
    [1, 3, 5, 7],
    [2, 4, 6],
    [0, 8, 9, 10, 11]
  ]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Example 2:

Input:
  [
    [1,2,3],
    [1,2]
  ]
Output: [1,1,2,2,3]

Challenge

Do it in O(N log k).

• _N - _is the total number of integers.

• _k - _is the number of arrays.

Solution

LintCode official - Heap (Priority Queue)

可以用堆做到 O(N log k) 的时间复杂度.

初始将所有数组的首个元素入堆, 并记录入堆的元素是属于哪个数组的.

每次取出堆顶元素, 并放入该元素所在数组的下一个元素.

/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/

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

public class Solution {
    private Comparator<Element> ElementComparator = new Comparator<Element>() {
        public int compare(Element left, Element right) {
            return left.val - right.val;
        }
    };

    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    public int[] mergekSortedArrays(int[][] arrays) {
        if (arrays == null) {
            return new int[0];
        }

        int total_size = 0;
        Queue<Element> Q = new PriorityQueue<Element>(
            arrays.length, ElementComparator);

        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                Element elem = new Element(i, 0, arrays[i][0]);
                Q.add(elem);
                total_size += arrays[i].length;
            }
        }

        int[] result = new int[total_size];
        int index = 0;
        while (!Q.isEmpty()) {
            Element elem = Q.poll();
            result[index++] = elem.val;
            if (elem.col + 1 < arrays[elem.row].length) {
                elem.col += 1;
                elem.val = arrays[elem.row][elem.col];
                Q.add(elem);
            }
        }

        return result;
    }
}

Divide and Conquer

public class Solution {
    /**
     * @param arrays: k sorted integer arrays
     * @return: a sorted array
     */
    public int[] mergekSortedArrays(int[][] arrays) {
        if(arrays == null || arrays.length == 0) return new int[0];
        return divide_conquer(arrays);
    }

    private int[] divide_conquer(int[][] arrays){
        while(arrays.length>1){
            int n = arrays.length/2;
            if(arrays.length%2 == 1) n++;

            int temp[][] = new int[n][];
            int idx = 0;
            for(int i=0;i<arrays.length && i+1<arrays.length; i+=2){
                temp[idx++] = mergeTwoSortedArray(arrays[i], arrays[i+1]);
            }
            if(arrays.length%2 == 1) temp[idx++] = arrays[arrays.length-1];

            arrays = temp;
        }
        return arrays[0];
    }


    private int[] mergeTwoSortedArray(int[] arr1, int[] arr2){
        if(arr1 == null || arr1.length == 0) return arr2;
        if(arr2 == null || arr2.length == 0) return arr1;

        int totalLen = arr1.length+arr2.length;
        int[] res = new int[totalLen];
        int idx=0;
        int i=0, j=0;

        while(i<arr1.length && j<arr2.length){
            if(arr1[i]<=arr2[j]){
                res[idx++] = arr1[i++];
            }else{
                res[idx++] = arr2[j++];
            }
        }

        while(i<arr1.length){
            res[idx++] = arr1[i++];
        }

        while(j<arr2.length){
            res[idx++] = arr2[j++];
        }

        return res;
    }
}