Geek asks and answers

Combining two sorted arrays in the third can be done in O (n)?

I am trying to combine to sort arrays into a third sorted array, but I do not see any way to do this in O(n), only in O(n*n). Am I mistaken? is there any way to do this in O(n)?

Edit:

Actually the question is a little different:

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

I'm thinking of:

  • put lists in two arrays

  • merge two arrays using MergeSort (this takes time O(n))

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

any ideas?

Hi

+3
source share
6

, 3- . arr1 arr2, arr1 arr3, "", arr2. /, .

O (n + m), aka O (n).

+10

:

= 1 [1,2,6,10]

= 2 [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).

+9

, , 0. , , , ( , ) , , .

, , .

, , O (n).

+1

: ( [] ).

0

, O (n * n)? , (3 ), O (n), O (n * n). O (n), O (n). -O . "-O" , .

0

, , O (n + m), n m - , .

:

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

, , , , .

0
source

More articles:


All Articles