반전 된리스트의 조합

Question

k 개의 정렬 된 반전리스트를 제공합니다.이 k 개의리스트의 합집합을 얻는 효율적인 알고리즘이 필요합니까? 각 반전 된 목록은 메모리의 읽기 전용 배열이며 각 목록에는 정렬 된 순서로 정수가 포함됩니다. 결과는 충분히 큰 사전 정의 된 배열에 저장됩니다. k-way 병합보다 나은 알고리즘이 있습니까?

Answer 1

K-Way 병합이 최적입니다. O(log(k)*n) ops [모든 목록의 요소 수를 합한 값은 n입니다.]

그것은 더 나은 할 수없는 경우를 참조하기 쉬운 - 그렇지 않으면 당신은 크기 1.

• 주의 덩어리 [반전 인덱스]로 분할하여 O(nlogn) 다음 어떤 배열이 잘 정렬 할 수 @jpalecek가 언급 한 바와 같이 : 이 대답은 반전 된 인덱스 [결과 배열]이 정렬되는 것이 중요하다고 가정합니다. 이 가정은 반전 된 인덱스를 사용하는 대부분의 응용 프로그램의 경우 특히 정보 검색 영역에서 해당됩니다. 이 [정렬 된 인덱스] 기능을 사용하면 인덱스를 쉽고 빠르게 교차 할 수 있습니다.
• 참고 : 표준 k-way 병합을 사용하면 중복이 허용되므로 을 사용해야합니다. 요소가 두 목록에 나타나는 경우 이 한 번만 추가됩니다. [마지막 요소를 확인하기 만하면됩니다. 추가하기 전에 대상 배열].

Answer 2

결과 배열을 정렬 할 필요가없는 경우 가장 좋은 방법은 해시 테이블을 사용하여 본 요소를 표시하는 것입니다. 이렇게하면 O(n) (전체 요소 수인 n) 시간 복잡도를 얻을 수 있습니다. (펄)의 라인을 따라

뭔가 :

이 목록에 포함되어 그것이 무엇을 의미 하는가 어떤 값