for 루프를 사용하는 것보다 정렬 된 두 목록에서 일치하는 것을 찾는 더 나은 방법? (Java)

Question

두 개의 정렬 된 목록을 둘 다 내림차순으로 있습니다. 예를 들어, 요소가 [2,3,4,5,6,7...] 인 하나의 정렬 된 링크 된 목록과 요소가 [5,6,7,8,9...] 인 다른 목록이 있습니다.

두 목록에서 공통된 요소를 모두 찾아야합니다. for 루프와 중첩 된 루프를 사용하여 모든 일치 항목을 반복하여 동일한 두 요소를 찾을 수 있음을 알고 있습니다. 그러나 실행 시간이 O(n^2) 미만인이 작업을 수행하는 다른 방법이 있습니까?

Answer 1

O (n) 시간에 할 수 있습니다. 의사 코드 :

a = list1.first 
b = list2.first 
repeat: 
    if a == b: 
     output a 
     a = list1.next 
     b = list2.next 
    elif a < b: 
     a = list1.next 
    else 
     b = list2.next 
until either list has no more elements 

Answer 2

첫 번째 목록을 HashSet; 각 요소가 HashSet에 있는지 여부를 확인하는 두 번째 목록을 반복합니다.

Answer 3

주 루프에서 두 목록의 첫 번째 요소를 가져와 비교해보십시오. 그것들이 동일하지 않은 경우, 다른 루프의 요소와 동일하거나 더 같아 질 때까지 더 적은 요소로 목록을 스캔하십시오. 평등하게되면 공통 요소를 발견하게됩니다. 공통 요소가 전달 될 때까지 두 목록을 순차적으로 읽습니다. 메인 루프를 계속하십시오. 이 접근법의 복잡성은 O (n + m)입니다.

Answer 4

사실 당신은 조금 더 작업을 수행 할 수 있습니다

def dropWhile(ls, cond): 
    if cond(ls[0]): return dropWhile(ls[1:], cond) 
    return ls 

def bisect(ls, v): 
    """ 
    Finds largest i s.t. ls[i]<=v and returns it. 
    If no such i exists it returns -1. 
    Runs in O(log n) 
    """ 
    pass 

def find_commons(ls1, ls2, ret): 
    if not (ls1 or ls2): return 
    i = bisect(ls2, ls1[0]) 
    if i<0: find_commons(ls2, ls1[1:], ret) 
    elif ls2[i]==ls1[0]: 
     ret.append(ls1[0]) 
     trim = lambda ls: dropWhile(lambda x: x==ls1[0], ls) 
     find_commons(trim(ls1), trim(ls2), ret) 
    else: find_commons(ls2[i+1:], ls1, ret)