合并两个有序阵列到第三个可以在O（n）是做什么？ [英] Merging two sorted arrays into a third one can be done in O(n)?

问题描述

我试图合并，排序数组到第三个排序的数组，但我看不到 没有办法做到在 O（N），只有在 O（N * N） .AM我错了吗？有没有办法做到这一点的 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

合并使用归并两个数组（这需要 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屋！