# 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) 的时间复杂度.

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

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

```java
/**
* 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

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/heap/merge-k-sorted-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.