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

Question

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

编辑:

实际上问题有点不同:

我有2个排序的跳过列表,我想将它们合并到一个新的排序跳过列表中,而不更改输入(即两个跳过列表).

我在考虑:

• 将列表放在两个数组中

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

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

有任何想法吗 ？

问候

Answer 1

你保持两个循环,当你从每个'side'中拉出值到第三个数组时,在它们之间翻转.如果arr1的值小于当前的arr2,那么将arr1的值填入arr3直到你达到相等或"更大",然后你翻转过程并开始从arr2中拉出值.然后继续反复弹跳,直到任何一个源阵列都没有留下任何东西.

出来是O(n + m),又名O(n).

Answer 2

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

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

等等..

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

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