logo标签列表

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

javaalgorithmsortingdata-structuresbig-o
4
尝试将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);
            }
        }
    }
}
这会使时间复杂度大于 Big-O(N)。实际上，通常可以达到的最佳性能大约为 O(N*lgN)，这比 O(N) 更糟糕。因此，在一个初始的 O(N) 操作中将三个数组放入一个单一的位置桶中，很可能不会影响排序的整体性能。 - Tim Biegeleisen
请了解分治算法，例如归并排序和快速排序。 - Tim Biegeleisen
如果我能够对这3个数组进行一次遍历，将最小值分配到最终数组中（就像上面的实现方式），那么时间复杂度怎么会超过O(N)呢？@TimBiegeleisen - Leonardo Lopez
这三个数组已经排序了吗？如果是的话，那么你可能能够在O(N)时间内完成。在一般情况下，这与任何其他排序问题没有区别。 - Tim Biegeleisen
合并排序数组的最佳情况是O(n log k)，其中n是总项目数，k是列表数。对于合并两个数组，这相当于O(n * log(2))，也就是O(n)。您的示例只是基于一般优先级队列的合并，硬编码条件取代了显式优先级队列。分析将显示，在最坏情况下比较次数为O(n log k)。 - Jim Mischel
有没有任何答案解决了你的问题？你可以留下评论或接受你选择的答案吗？ - trincot
5个回答
4

你的思路正确，是一个O(n)的解决方案。然而，在你的代码中确实存在一些问题，其中有一些将导致数组越界异常：

  • 你在没有先确保k < c.length的情况下访问了c[k]；
  • 即使你确实对length进行了测试，但你的方式并不能避免这种无效的访问：(i != a.length || j != b.length) && a[i] < b[j]仍然会导致在i === a.length时访问a[i]（尤其是当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上查看其运行情况。

有趣的是，这段代码实际上只是标准优先队列基于k路归并的一种实现，针对k == 3的情况进行了硬编码。你会注意到，在最坏情况下比较次数为O(n log k)，而不是O(n)。 - Jim Mischel
4
比较次数的数量确实是O(n logk)，但由于在这个问题中k是一个常数，因此我们可以说它是*O(n)*。 - trincot
2
请按照以下步骤操作：

事实上，玩弄数组索引非常令人沮丧。如果您可以将这些数组作为队列或迭代器获取，只需在每次迭代中 take() 或 next() 最小值并将其放入结果列表中，它会更加清晰。

@trincot 我可能错过了这个，抱歉。 - Tim Biegeleisen
抱歉，但这不是O(n)。如果您将示例扩展到5个数组，您很容易就能看出复杂度大于O(n)。第一次查看数组a和b。然后查看ab和c。然后是abc和d等等。最坏情况下的复杂度为O(k^2 * n)，其中k是列表数，n是所有项的总数。当然，如果您说k是常数，那么，是的，我想您可以说该算法是O(n)。此外，即使有三个数组，您执行的比较次数也取决于合并数组的顺序。 - Jim Mischel
我知道这点，但问题中说了“3个已排序数组”。决定k是一个常数的并不是我。我认为我的解决方案非常优秀，如果Dijkstra还活着，他肯定会对它印象深刻（滑稽）。 - Nicomak
0

你需要清楚地了解N的变化。如果你总是只有三个数组，它们的大小或最大大小随着N的变化而改变，那么几乎任何代码都可以重复选择任意三个数组中可用的最小数字，将其删除，并将其附加到结果数组的末尾，这将是O（N）的。你选择最小数字的代码可能很笨拙和昂贵，但它只是一个不随N增加而改变的常数因子。

如果要合并的数组数量随N增加，则需要更加谨慎地选择可用的最小数字，最终你将面临一个排序问题，在通常的假设下无法在线性时间内完成。

通常情况下，外部排序将使用堆（例如http://www.geeksforgeeks.org/external-sorting/）合并存储在磁盘上的大量列表。这将更有效地合并大量列表，但只会为你节省一个常数因子。

0
假设这是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;
}
0

如果逻辑对你来说很简单，请勾选此选项。
逻辑： 从3个数组中识别出最小的元素，并将其添加到合并数组中。 同时也要处理如果所有的数组元素都被覆盖（已添加到合并数组中）的情况，即在最小数计算中忽略该数组。

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]

在replit上检查输出

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接