이 두 목록

Question

의 주문이 알고리즘은 목록 1

목록 1 일치 O (N^2) 재 주문 목록 2에 대한보다 거기에 비교 BDCA

참고 : 목록 2는 목록 1과 비교하여 더 많거나 적거나 완전히 다른 항목을 가질 수 있습니다.

Answer 1

목록의 항목 유형에 대해 전체 주문을 만들 수있는 경우 목록 1의 색인을 만들 수 있습니다. 항목을 정렬합니다. 그런 다음이 색인을 사용하여 목록 2의 순서를 바꿀 수 있습니다.이 알고리즘은 시간상 O (n log n)이며 공간에 여분의 O (n)이 필요합니다.

Answer 2

O (n Log (n))가되는 한 가지 가능성은 다음과 같습니다. 이를 위해서는 목록 값을 배열/벡터/정렬 가능한 구조 유형으로 읽어야합니다.

• 값에 따라 목록 1을 정렬하고 위치 정보를 유지해야합니다. 이렇게하면 항목을 찾고 해당 위치를 알 수있는 빠른 방법을 제공합니다. 정렬 비용은 O (n log n)
• 입니다. 첫 번째 단계의 정렬 된 목록을 비교 함수로 사용하여 목록 2를 정렬합니다. 두 개는 두 값을 비교하고, 정렬 된 목록에서 결과를 찾은 다음 두 값 간의 비교로 상대 위치를 사용합니다. 이 종류의 비용 또한 O (n log n)입니다.

편집 후에는 두 번째 목록에 첫 번째 목록과 상관 관계가 없음을 언급합니다. 따라서 비교 함수는이를 고려해야합니다. 비교되는 값 중 하나 또는 둘 모두가 첫 번째 목록에없는 경우 compare 함수는 값의 순서를 결정해야합니다 (예 : 끝에 또는 처음으로 이동합니까?).

Answer 3

당신은 Diff Algorithm을 찾고 있습니다!