将两个已排序的数组合并为第三个数组可以在O(n)中完成吗?

I'm trying to merge to sorted arrays into a third sorted array , but I can't see any way to do that in O(n) , only in O(n*n) .Am I wrong ? is there a way to do that in O(n) ?

我尝试将数组合并到一个有序数组中，但是在O(n)中我看不到任何方法，只有O(n*n)，我错了吗?在O(n)中有这样的方法吗?

Edit :

编辑:

Actually the question is a little different :

实际上问题有点不同:

I have 2 sorted skip lists and I want to merge them into a new sorted skip list ,without changing the input (i.e. the two skip lists) .

我有两个排序过的跳转列表，我想将它们合并到一个新的排序过的跳转列表中，而不改变输入(即两个跳转列表)。

I was thinking about :

我在想:

put the lists in two arrays

将列表放在两个数组中
merge the two arrays using MergeSort (this takes O(n) runtime)

使用归并排序合并两个数组(这需要O(n)运行时)
build a new skip list from the sorted array .... // I'm not sure about its runtime

建立一个新的跳跃表排序的数组....//我不确定它的运行时间

any ideas ?

什么好主意吗?

Regards

问候

6 个解决方案

#1

You keep two loops going, and flip between each of them as you pull values from each 'side' into the 3rd array. if arr1's values are less than the current arr2, then stuff arr1's values into arr3 until you hit equality or go 'bigger', then you flip the process and start pulling values out of arr2. And then just keep bouncing back/forth until there's nothing left in either source array.

你保留两个循环，当你从每一个“侧”到第3个数组中拉值时，在它们之间来回切换。如果arr1的值小于当前的arr2，那么将arr1的值放到arr3中，直到你达到相等或“更大”，然后你翻转这个过程，开始从arr2中拉出值。然后不断地来回弹跳直到两个源数组中都没有剩余。

Comes out to O(n+m), aka O(n).

得到O(n+m)也就是O(n)

#2

picture two arrays one above the other:

图片两个数组一个在另一个上面:

list1=[1,2,6,10]

list1 =(1、2、6、10)

list2=[3,4,10]

用于=(3、4、10)

if we start from the left and work our way to the right, comparing the items, each time we take the smallest value and put it in the third array. From the list that we took the smallest item from, we move onto its next item.

如果我们从左边开始，一直到右边，比较项目，每次我们取最小的值并把它放到第三个数组中。从我们取最小项的列表中，我们转到它的下一个项。

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..

等。

until we get the final merged array [1,2,3,..]

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

Because selecting each element for the third array only took one move, it's basically O(N).

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

#3

you can use two index variables for the already sorted array, and another one for the array being sorted, all initialized to 0. Now, while you haven't reached the end with any of the sorted arrays, compare the two pointed values in each iteration, take the higher (or lower, depends on your sorting) value and increment the index pointing to the value you've just used.

对于已经排序的数组，可以使用两个索引变量，而对于正在排序的数组，可以使用另一个索引变量，它们都初始化为0。现在，当您还没有完成任何排序数组的末尾时，请在每次迭代中比较两个值，取较高(或较低，取决于您的排序)值，并增加指向刚才使用的值的索引。

At the end, go through the array you havn't completed and just paste the remaining values into the merged array.

最后，遍历尚未完成的数组并将其余值粘贴到合并数组中。

That way, you're going through the values only once, meaning O(n).

这样，你只遍历一次值，也就是O(n)

#4

Hint: consider only the head elements of both lists (and remove them [virtually] when processed).

提示:只考虑两个列表的头元素(并在处理时删除它们)。

#5

If both input lists are already sorted, how could the merge be O(n*n)? The algorithm given by yourself (the 3 steps) is definitely O(n) rather than O(n*n). Each step is O(n), so overall it is O(n). The big-O is determined by the highest order of your algorithm. Be sure to understand the concept of big-O before working on your homework.

如果两个输入列表都已排序，那么合并怎么会是O(n*n)呢?你自己给出的算法(三个步骤)肯定是O(n)而不是O(n*n)。每一步都是O(n)所以总的来说是O(n)大o由算法的最高阶决定。在做作业之前，一定要理解big-O的概念。

#6

Yes it can be done, actually it would be O(n + m) where n and m are length of first and second arrays, consecutively.

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

The algorithm is called one pass merge

这种算法叫做一遍归并

Pseudo code:

伪代码:

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

Basically, you traverse both arrays at the same time and if the lengths are different, larger array won't be traversed all the way up, so you just add all the elements of the larger array to the result.

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

#1