다른 크기의 두 배열에서 공통 요소 찾기

Question

다른 크기의 두 배열의 공통 요소를 얻는 가장 좋은 방법을 찾아야합니다.

배열의 순서는 동일하지 않습니다. 공통 요소는 다른 위치에 있지만, 동일한 순서로 최대 거리 N.와 (배열에서 일반적인 요소 B가 후에 온 경우, 동일 어레이 B의 발생)과

I '는 수 O (N)의 추가 공간을 사용하십시오.

실제로 배열 A에서 N 요소를 추출하고 mergesort로 순서를 지정하고 배열 B의 N 요소를 사용하여 dicotomic 검색을 수행합니다. 그런 다음 찾은 일치 항목의 위치에서 다음 N 요소를 가져 와서 다른주기를 수행합니다.

이 비용은 미터는 어레이 B의 길이로, O (m N 로그 N)이

제가 시도 이용한 해시 테이블을 사용하지만 목록을 구현할 수있는 충돌을 관리 할 수 ​​있어야 효율성이 떨어집니다.

더 좋은 방법이 있습니까?

Answer 1

당신은 아마 당신의 일치 순서에서 "구멍"(A = [1,3,2]와 B = [-1,4,2- 다음 MatchSet = {1,2})

을 가질 수 있습니다 가정 I 잘못입니다 그러나 당신이 의사 코드 시도 할 수 있습니다 : (A)의 다음 요소로

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 

첫 번째 인덱스 (I) 포인트 반면 B에서 찾을 수 없습니다 (J)가 B의 다음 요소를 찾기 위해 사용된다 (이후 마지막 요소는 A).

이 yould는 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