Поиск общих элементов в двух массивах разного размера

Question

Мне нужно найти лучший способ получить общие элементы из двух массивов разного размера.

Массивы неупорядочены; общие элементы находятся в другом положении, но в том же порядке (если в массиве Общим элементом б пришел после того, как , то же самое происходит в массиве B), и с максимальным расстоянием N.

могу» t используйте дополнительное пространство O (N).

Фактически я извлекаю N элементов из массива A, заказываю их с помощью mergesort и выполняю двукоординатный поиск с использованием N элементов массива B. Затем я получаю следующие N элементов из позиции найденного совпадения и выполняю другой цикл.

Стоимость это должно быть, используя м как длина массива В, О (м Н журнал N)

Я попытался с помощью хеш-таблицы, но для управления столкновений я должен реализовать список, и эффективность снижается.

Есть лучший способ?

Answer 1

Предполагая, что вы можете иметь "дыры" в вашей согласованной последовательности (A = [1,3,2] и В = [1,4,2] Тогда MatchSet = {1,2})

Может быть, я я ошибаюсь, но вы можете попробовать этот псевдо код:

i <- 0; j <- 0; jHit <- -1 
matchSet <- Empty 
While i < Length(A) AND j < Length(B): 
    If A[i] == B[j] Then 
     matchSet.add(A[i]) 
     i <- i+1 
     jHit <- j 
    End If 
    j <- j+1 
    If j == Length(B) Then 
     i <- i+1 
     j <- jHit+1 
    End If 
End Loop 

Первый индекс (я) указывает на следующий элемент а, не найден в B, тогда как (J) используется для поиска следующего элемента B (после последний элемент, найденный в A).

Это дает вам временную сложность O (mN) и использование пространства O (N).

Здесь есть реализация в Python:

def match(A,B): 
    i = 0 
    j = 0 
    jHit = -1 
    res = [] 
    while i < len(A) and j < len(B): 
     if A[i] == B[j]: 
      res.append(A[i]) 
      i += 1 
      jHit = j 
     j += 1 
     if j == len(B): 
      i += 1 
      j = jHit+1 
    return res