如何在 Big-O(N) 时间内将 3 个排序数组合并为 1 个排序数组？

Question

正在尝试将 3 个数组合并为一个，以便最终数组按顺序排列。

给定

int[] a = {1,3};
int[] b = {2,4};
int[] c = {1,5};

合并数组使得最终数组 d = {1,1,2,3,4,5}

不能只是连接它们然后对 d 数组进行排序，因为那样会使时间复杂度大于 Big-O(N)。

这就是我到目前为止所得到的。遇到索引超出范围的问题：

public static void main(String[] args) {
    // Sort these 3 arrays. The final array should be d = {1,1,2,3,4,5}
    int[] a = {1,3};
    int[] b = {2,4};
    int[] c = {1,5};
    int[] d = new int[a.length + b.length + c.length];

    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;

    for (int iteration = 0; iteration <= d.length; iteration++){
        if ((i != a.length || j != b.length) && a[i] < b[j]){
            if (a[i] < c[k]){
                // then a[i] is smallest
                d[l] = a[i];
                i++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (a[i] > c[k]){
                // then c[k] is smallest
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (a[i] == c[k]){
                d[l] = a[i];
                i++;
                l++;
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
        }
        else if(b[j] < a[i]){
            if (b[j] < c[k]){
                // b[j] is smallest
                d[l] = b[j];
                l++;
                j++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (b[j] > c[k]){
                // c[k] is smallest
                d[l] = c[k];
                l++;
                k++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (b[j] == c[k]){
                d[l] = b[j];
                j++;
                l++;
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
        }
    }
}

Answer 1

按照以下步骤操作：

从这里获取答案代码：How to merge two sorted arrays into a sorted array?
在 a 和 b 上调用该函数以获得结果数组 ab
在 ab 和 c 上调用该函数以获得结果 abc
您已经调用了一个 O(n) 函数两次，所以它仍然是 O(n)。砰。

事实是，摆弄数组索引令人沮丧。如果您可以将这些数组作为队列或迭代器来代替，只需 take() 或 next() 每次迭代中的最小值并将其放入结果列表中，它将更清晰。

Answer 2

您需要清楚什么随 N 发生变化。如果您总是只有三个数组，并且它们的大小或最大大小随 N 发生变化，那么几乎所有重复 selects 最小数字的代码从三个数组中的任何一个可用，将其删除并将其附加到结果数组的末尾，将是 O(N)。您的 select 最小数字的代码可能笨拙且昂贵，但它只是一个常数因子，不会随着 N 的增加而改变。

如果要合并的数组数量随着 N 的增加而增加，那么您需要更加小心select 可用的最小数量，您最终会遇到排序问题，您可以'在通常的假设下，t 在线性时间内完成。

通常，外部排序会使用堆合并磁盘上保存的大量列表（例如 http://www.geeksforgeeks.org/external-sorting/）。这对于一次合并大量列表会更有效率，但只会让你获得一个常数因子，

Answer 3

假设这是 java，数组名是对数组的引用，可以像 C/C++ 中的指针一样交换。这可用于减少主合并循环中的条件数量，使代码更简单一些，但代价是交换。空数组检查在主合并循环之前完成。此方法可以轻松扩展以处理 4 路或更大的合并，否则需要大量条件。

static int[] Merge(int[] a, int[] b, int[] c)
{
    int[] d = new int[a.length + b.length + c.length];
    int[] e;   // temp used for swap
    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
    int t;
    // empty array checks
    if(0 == b.length){      // if b empty
        if(0 == c.length){  // if b and c empty
            c = a;          //   c = a
            a = b;          //   a = b = empty
        } else {            // if b empty, c not empty
            e = a;          //   swap a and b
            a = b;
            b = e;
        }
    } else {                // else b not empty
        if(0 == c.length){  // if c empty
            e = c;
            c = b;          //   shift c = b, b = a
            b = a;
            a = e;          //   a = empty
        }
    }
    // main merge loop
    while(i < a.length){    // 3 way merge
        if(a[i] > b[j]){    // if b smaller swap
            e = a;
            a = b;
            b = e;
            t = i;
            i = j;
            j = t;
        }
        if(a[i] > c[k]){    // if c smaller swap
            e = a;
            a = c;
            c = e;
            t = i;
            i = k;
            k = t;
        }
        d[l++] = a[i++];
    }
    while(j < b.length){    // 2 way merge
        if(b[j] > c[k]){    // if c smaller swap
            e = b;
            b = c;
            c = e;
            t = j;
            j = k;
            k = t;
        }
        d[l++] = b[j++];
    }
    while(k < c.length)     // copy rest of c
        d[l++] = c[k++];
    return d;
}

Answer 4

你的想法是正确的，代表了一个 O(n) 的解决方案。但是，你的代码确实存在一些问题，其中一些会导致越界异常：

您访问 c[k] 时未先确保 k < c.length;
即使您在 length 上做测试，您也无法避免这种无效访问：(i != a.length || j != b.length) && a[i] < b[j] 仍然会导致a[i] 在 i === a.length 时被访问（特别是在 j != b.length 时）；
外循环需要迭代的次数通常是错误的，因为有时（在相等的情况下）您将两个值存储在目标数组中，这使得数组填满的速度比循环预期的要快。其实相等的情况（比如a[i] == c[k]）其实并不需要单独对待。如果将它与 > 一起处理（因此：>=）算法仍然正确：第二个（相等的）值将在下一次迭代中复制；
即使您解决了上一个问题，您的外循环仍然使一次迭代过多； for 条件应该是 < d.length 而不是 <= d.length

没有问题，但是你的代码中有很多重复：

您可以将对 displayArrayContents(a,b,c,d,i,j,k,l); 的调用移到 if 构造之外，这样它就会始终执行，这正是您真正想要的；
由于您总是在 if 构造中分配给 d，因此您可以使用三元运算符 ? ... :;

if

虽然像 i != a.length 这样的测试可以达到预期目的，但最好还是像这样进行测试：i < a.length。

这里是考虑了上述因素的代码：

import java.util.Arrays; // for easy output of arrays with Arrays.toString().

class Main {
  public static void main(String[] args) {
    // Sort these 3 arrays. The final array should be d = {1,1,2,3,4,5}
    int[] a = {1,3};
    int[] b = {2,4};
    int[] c = {1,5};
    int[] d = new int[a.length + b.length + c.length];

    int i = 0;
    int j = 0;
    int k = 0;
    for (int l = 0; l < d.length; l++) {
      d[l] = i < a.length && (j >= b.length || a[i] < b[j])
                ? (k >= c.length || a[i] < c[k]
                    ? a[i++]
                    : c[k++])
                : (j < b.length && (k >= c.length || b[j] < c[k])
                    ? b[j++]
                    : c[k++]);
       // Uncomment this if you still need it:
       //displayArrayContents(a,b,c,d,i,j,k,l); 
    }

    System.out.println(Arrays.toString(d));
  }
}

最后一条语句的输出：

[1, 1, 2, 3, 4, 5]

在 repl.it 上查看运行。

Answer 5

如果您觉得逻辑简单，请勾选此项。
逻辑：从 3 个数组中找出最小的元素并将其添加到 mergeArray 中。如果数组的所有元素都被覆盖（添加到 mergedArray 中），也可以处理，即从最小数字计算中忽略该数组。

import java.util.Arrays;

public class SortingAlgo {


    public static void main(String[] args) {

        int[] arr1 = {1,4,7,12,15,16,19,26,26, 29,35};
        int[] arr2 = { 3,8,12,14,40, 44, 45};
        int[] arr3 = {2,4,29, 30};


        int[] merged = getMerged(arr1, arr2, arr3);

        System.out.println(Arrays.toString(merged));
       
    }

  

    private static int[] getMerged(int[] arr1, int[] arr2, int[] arr3) {
        int[] merged = new int[ arr1.length + arr2.length + arr3.length];

        int i = 0; // Merged index
        int i1 = 0, i2=0, i3=0; // for arr1, arr2, arr3
        boolean i1Completed = false, i2Completed = false, i3Completed = false;

        while(i1 < arr1.length || i2 < arr2.length || i3 < arr3.length) {
            if(!i1Completed && (i2Completed || arr1[i1] <= arr2[i2]) &&  (i3Completed || arr1[i1] <= arr3[i3]  )){
                merged[i++] = arr1[i1++];  // arr1 element smallest
                if(i1 == arr1.length)
                    i1Completed = true;

            } else if(!i2Completed && (i1Completed || arr2[i2] <= arr1[i1] ) &&  ( i3Completed || arr2[i2] <= arr3[i3]) ){
                merged[i++] = arr2[i2++];

                if(i2 == arr2.length)
                    i2Completed = true;

            } else if(!i3Completed && ( i2Completed ||  arr3[i3] <= arr2[i2] ) && ( i1Completed ||  arr3[i3] <= arr1[i1]) ){
                merged[i++] = arr3[i3++];

                if(i3 == arr3.length)
                    i3Completed = true;

            }

        }
        return merged;
    }

}

输出：[1, 2, 3, 4, 4, 7, 8, 12, 12, 14, 15, 16, 19, 26, 26, 29, 29, 30, 35, 40, 44, 45]

check output at replit

如何在 Big-O(N) 时间内将 3 个排序数组合并为 1 个排序数组？

How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?

java

sorting

algorithm

big-o

data-structures