可以在 O(n) 中完成将两个排序的数组合并到第三个数组中吗? [英] Merging two sorted arrays into a third one can be done in O(n)?

问题描述

我正在尝试将已排序数组合并到第三个已排序数组中，但我看不到任何方法都可以在 O(n) 中做到这一点，只有在 O(n*n) 中.我错了吗?有没有办法在 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) ?

其实这个问题有点不同:

Actually the question is a little different :

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

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

我在想:

• 将列表放在两个数组中

• put the lists in two arrays

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

merge the two arrays using MergeSort (this takes O(n) runtime)

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

build a new skip list from the sorted array .... // I'm not sure about its runtime

有什么想法吗?

问候

推荐答案

您保持两个循环，并在将每个边"的值拉入第三个数组时在每个循环之间切换.如果 arr1 的值小于当前的 arr2，则将 arr1 的值填充到 arr3 中，直到达到相等或更大"为止，然后翻转该过程并开始从 arr2 中提取值.然后继续来回弹跳，直到两个源数组中都没有剩余.

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.

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

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

这篇关于可以在 O(n) 中完成将两个排序的数组合并到第三个数组中吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！