문제는 크기 n과 m의 중복이없는 두 개의 정렬 된 목록으로 구성됩니다. 첫 번째 목록에는 두 번째 목록에서 삭제해야하는 문자열이 포함됩니다.목록에서 항목 제거 - 알고리즘 시간 복잡도
가장 간단한 알고리즘은 nxm 작업을 수행해야합니다 (이 용어는 "2 차 시간"이라고 생각합니다).
향상된 솔루션은 두 목록이 모두 정렬되고 이후 비교에서 마지막으로 삭제 된 인덱스보다 낮은 인덱스의 문자열을 건너 뜁니다. 시간이 얼마나 복잡할까요?
시간 복잡성을 개선하기 위해이 문제에 대한 해결책이 있습니까?
Merge sort을 조사해야합니다. 이것이 왜 효과적으로 작동하는지에 대한 기본 아이디어입니다.
아이디어는 O(n+m) 시간이 걸립니다 함께 두 목록을 검사하는 것입니다 :
가 첫 번째 목록에 대한 포인터 x 확인을 A 말을하고 두 번째 목록에 대한 또 다른 포인터 y는 B을 말한다. x=0 및 y=0으로 설정하십시오. x < n 및 y < m 인 경우 A[x] < B[y] 인 경우 A[x]을 새 병합 된 목록에 추가하고 x을 증가시킵니다. 그렇지 않은 경우 B[y]을 새 목록에 추가하고 y을 증가 시키십시오. x=n 또는 y=m을 클릭하면 나머지 요소를 각각 B 또는 A에서 가져옵니다.
각 목록의 모든 항목이 정확히 한 번 방문되기 때문에 복잡도는 O(n+m)으로 추정됩니다.
두 번째 목록의 각 문자열이 버킷 인 경우 계산/버킷 정렬 알고리즘이 작동합니다.
두 번째 목록 (m 시간 소요)을 거치고 버킷을 만듭니다. 그런 다음 첫 번째 목록 (n 시간 소요)을 거쳐 발생 횟수를 늘립니다. 그런 다음 각 버킷 (m 시간 소요)을 다시 거쳐야하며 한 번 발생하는 문자열 만 반환해야합니다. Trie 또는 HashMap은 버킷을 저장하는 데 적합합니다. O (n + m + m) 여야합니다. 카운터를 증가시키는 대신 두 번째 단계에서 HashSet을 사용하면 Set에서 제거됩니다. 그것은 O (n + m + (m-n))이어야합니다.
제목을 좀 더 유용하게 바꾸십시오. – Thomash