使用 mergeSort 中的合并算法合并大小为 n 的 K 排序数组

Question

>问题：给定每个大小为 N 的 K 个排序数组，合并它们并打印排序后的输出。

Sample Input-1:
K = 3, N =  4
arr[][] = { {1, 3, 5, 7},
            {2, 4, 6, 8},
            {0, 9, 10, 11}} ;

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

我知道有一种方法可以使用优先级队列/最小堆来解决此问题，但我想使用 mergeSort 中的合并过程来解决这个问题。这个想法似乎很简单...在每次迭代中，将剩余的数组合并为两个一组，以便在每次迭代时数组数量减半。

但是，每当减半导致奇数时，这就会出现问题。我的想法是，每当减半导致奇数时，我们都会通过将它与上次合并形成的数组合并来处理额外的数组。

到目前为止，我拥有的代码如下。但是，这仅适用于 30 个测试用例中的一个：

static int[] mergeArrays(int[][] arr) {
        int k = arr.length;
        int n = arr[0].length;
        if(k < 2){
            return arr[0];
        }
        boolean odd_k;
        if(k%2){
            odd_k = false;
        }
        else{
            odd_k = true;
        }
        while(k > 1){
            int o;
            if(odd_k){
                o = (k/2) + 1;
            }
            else{
                o = k/2;
            }
            int[][] out = new int[o][];
            for(int i=0; i < k; i = i + 2){
                int[] a;
                int[] b;
                if(odd_k && i == (k-1)){
                    b = arr[i];
                    b = out[i-1];
                }
                else{
                    a = arr[i];
                    b = arr[i+1];
                }
                out[i] = mergeTwo(a, b);
            }
            k = k/2;
            if(k % 2 == 0){
                odd_k = false;
            }
            else{
                odd_k = true;
            }
            arr = out;
        }
        return arr[0];
    }
    static int[] mergeTwo(int[] a, int[] b){
        int[] c = new int[a.length + b.length];
        int i, j, k;
        i = j = k = 0;
       while(i < a.length && j < b.length){
           if(a[i] < b[j]){
               c[k] = a[i];
               i++;
               k++;
           }
           else{
               c[k] = b[j];
               j++; k++;
            }
       }
       if(i < a.length){
           while(i < a.length){
               c[k] = a[i];
               i++; k++;
           }
       }
       if(j < b.length){
           while(j < b.length){
               c[k] = b[j];
               j++; k++;
           }
       }
       return c;
    }

Answer 1

我们可以缩短您的mergeTwo实现，

static int[] mergeTwo(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int i = 0, j = 0, k = 0; // declare and initialize on one line
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++]; // increment and assign
        } else {
            c[k++] = b[j++]; // increment and assign
        }
    }
    // No need for extra if(s)
    while (i < a.length) {
        c[k++] = a[i++];
    }
    while (j < b.length) {
        c[k++] = b[j++];
    }
    return c;
}

然后，我们可以修复您的mergeArrays并通过从int[][]的第一行开始，然后使用 mergeTwo 迭代连接数组来缩短它。喜欢

static int[] mergeArrays(int[][] arr) {
    int[] t = arr[0];
    for (int i = 1; i < arr.length; i++) {
        t = mergeTwo(t, arr[i]);
    }
    return t;
}

然后我用

public static void main(String[] args) {
    int arr[][] = { { 1, 3, 5, 7 }, { 2, 4, 6, 8 }, { 0, 9, 10, 11 } };
    System.out.println(Arrays.toString(mergeArrays(arr)));
}

我得到（如预期的那样）

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

Answer 2

正如您所说，您一次合并了两个数组。由于效率低下，您可以同时合并所有子数组。你要做的是从每个子数组中找到最小值，并记住该元素的位置。

---

为此，我们可以使用另一个数组（例如curPos）来记住当前位置

 private int[] merge(int[][] arr) 
{
    int K = arr.length;
    int N = arr[0].length;
    /** array to keep track of non considered positions in subarrays **/
    int[] curPos = new int[K];
    /** final merged array **/
    int[] mergedArray = new int[K * N];
    int p = 0;
    while (p < K * N)
    {
        int min = Integer.MAX_VALUE;
        int minPos = -1;
        /** search for least element **/
        for (int i = 0; i < K; i++)
        {
            if (curPos[i] < N)
            {
                if (arr[i][curPos[i]] < min)
                {
                    min = arr[i][curPos[i]];
                    minPos = i;
                }
            }                
        }
        curPos[minPos]++;            
        mergedArray[p++] = min;
    }
    return mergedArray;

Answer 3

处理此问题的最简单方法可能是使用数组队列。最初，将所有数组添加到队列中。然后，从队列中删除前两个数组，合并它们，并将生成的数组添加到队列中。继续执行此操作，直到队列中只有一个数组。像这样：

for each array in list of arrays
    queue.push(array)
while queue.length > 1
    a1 = queue.pop()
    a2 = queue.pop()
    a3 = merge(a1, a2)
    queue.push(a3)
result = queue.pop()

这大大简化了事情，"减半"的问题消失了。