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

Question

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

编辑:

实际上这个问题有点不同:

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

我在想:

• 将列表放入两个数组中

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

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

有什么想法吗？

问候

Answer 1

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

结果为 O(n+m)，又名 O(n)。