3

我正在尝试将排序数组合并到第三个排序数组中，但我看不到任何方法可以做到这一点O(n)，只有在O(n*n)。我错了吗？有没有办法做到这一点O(n)？

编辑 ：

其实这个问题有点不同：

我有 2 个排序的跳过列表，我想将它们合并到一个新的排序跳过列表中，而不更改输入（即两个跳过列表）。

我在想：

  • 将列表放在两个数组中

  • 使用 MergeSort 合并两个数组（这需要O(n)运行时）

  • 从排序后的数组中构建一个新的跳过列表 .... // 我不确定它的运行时间

有任何想法吗 ？

问候

4

6 回答 6

10

您保持两个循环进行，并在将每个“边”中的值拉入第三个数组时在每个循环之间翻转。如果 arr1 的值小于当前的 arr2，则将 arr1 的值填充到 arr3 中，直到达到相等或“更大”，然后翻转过程并开始从 arr2 中提取值。然后继续来回弹跳，直到两个源数组中都没有任何东西。

结果为 O(n+m)，也就是 O(n)。

于 2012-05-01T04:46:13.553 回答
9

图片两个阵列一个在另一个之上：

list1=[1,2,6,10]

list2=[3,4,10]

如果我们从左边开始往右边走，比较项目，每次我们取最小值并将其放入第三个数组中。从我们从中取出最小项目的列表中，我们移至下一个项目。

i=0,j=0
list1[i] < list2[j]
take 1
i+=1
2<3
take 2
i+=1
3<6
take 3
j+=1

ETC..

直到我们得到最终的合并数组 [1,2,3,..]

因为为第三个数组选择每个元素只需要一步，基本上是 O(N)。

于 2012-05-01T04:47:52.840 回答
1

您可以为已排序的数组使用两个索引变量，为正在排序的数组使用另一个索引变量，全部初始化为 0。现在，虽然您还没有到达任何排序数组的末尾，但比较每个中的两个指向值迭代，取更高（或更低，取决于您的排序）值并增加指向您刚刚使用的值的索引。

最后，浏览您尚未完成的数组，然后将剩余的值粘贴到合并的数组中。

这样，您只需要遍历一次值，即 O(n)。

于 2012-05-01T04:52:08.310 回答
0

提示：只考虑两个列表的头元素（并在处理时[虚拟地]删除它们）。

于 2012-05-01T04:47:03.083 回答
0

如果两个输入列表都已排序，那么合并怎么可能是 O(n*n)？自己给的算法（3个步骤）肯定是O(n)而不是O(n*n)。每一步都是O(n)，所以总体来说是O(n)。big-O 由算法的最高阶决定。在做作业之前一定要了解大 O 的概念。

于 2012-05-01T09:59:54.493 回答
0

是的，它可以做到，实际上它是O(n + m)，其中 n 和 m 是第一个和第二个数组的长度，连续。

该算法称为一次通过合并

伪代码：

i, j, k = 0 // k is index for resulting array
//maximum length of the resulting array can be n+m, 
//so it is always safe to malloc for such a length if you are in C or C++

while(i< len(array1) and j < len(array2) )
     if (array1[i] == array2[j])
           result[k] = array1[i]
           ++i, ++j, ++k
     else if (array1[i] < array2[j])
           result[k] = array1[i]
           ++i, ++k
     else
           result[k] = array2[j] 
           ++j, ++k

//now one array might not be traversed all the way up
if ( i < len(array1) )
      while( i != len(array1))
            result[k] =  array1[i]
            ++i, ++k

else if ( j < len(array2) )
      while( j != len(array2) )
            result[k] = array2[j]
            ++j, ++k

基本上，您同时遍历两个数组，如果长度不同，则不会一直遍历较大的数组，因此您只需将较大数组的所有元素添加到结果中。

于 2016-12-24T03:10:09.223 回答