我正在尝试将排序数组合并到第三个排序数组中，但我看不到任何方法可以做到这一点O(n)，只有在O(n*n)。我错了吗？有没有办法做到这一点O(n)？
编辑 ：
其实这个问题有点不同：
我有 2 个排序的跳过列表，我想将它们合并到一个新的排序跳过列表中，而不更改输入（即两个跳过列表）。
我在想：
将列表放在两个数组中
使用 MergeSort 合并两个数组（这需要
O(n)运行时）从排序后的数组中构建一个新的跳过列表 .... // 我不确定它的运行时间
有任何想法吗 ？
问候
问问题
10104 次
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 回答