두 개의 연결된 목록의 드문 요소를 얻는 방법은 무엇입니까?

Question

두 개의 연결된 정수 목록이 제공됩니다. 비 공통 요소를 포함하는 연결된 목록을 반환하라는 요청을 받았습니다. 나는 O (n^2)에서 그것을하는 법을 알고 있습니다. O (n)에서 그것을하는 방법은 무엇입니까?

Answer 1

분류되지 않은 경우 O (n^2)보다 더 좋아질 수 있다고 생각하지 않습니다. 그러나, 당신은 그들을 정렬하여 더 잘할 수 있습니다 ... 당신은 합리적으로 빠른 시간에 정렬하고 O (nlogn)과 같은 것을 얻을 수 있습니다 (나는 그것이 될 것이라고 확신하지 않지만, 나는 그렇게 빨리 될 수 있다고 생각합니다. 당신은 올바른 알고리즘을 사용합니다).

Answer 2

해시 테이블을 사용하십시오.

첫 번째 연결된 목록을 반복하고 해시 테이블에 들어온 값을 입력하십시오.

해시 테이블에없는 요소를 비 일반적인 요소 목록에 추가하여 두 번째 연결된 목록을 반복합니다.

해시 테이블에서 충돌이 없다고 가정하면이 솔루션은 O (n)이어야합니다.

Answer 3

빈 목록을 새로 만듭니다. 해시 테이블을 가지고 두 목록의 요소로 채 웁니다. 복잡성 n. 순차적으로 각 목록을 반복하고 반복하면서 해시 테이블에없는 요소를 새 목록에 넣습니다. 복잡성 n. 전반적인 복잡도 = n