정수 배열 (예 : [1 5 3 4 6])이 있다고 가정합니다. 요소는 다음 규칙에 따라 재정렬됩니다. 모든 요소는 앞으로 건너 뛰어 (왼쪽으로) 건너 뛴 색인의 요소를 슬라이드 할 수 있습니다. 프로세스는 두 번째 인덱스의 요소 (즉, 5)로 시작합니다. 요소 1을 건너 뛸 수있는 선택권이 있거나 자신의 위치에 머무를 수 있습니다. 이동하기로 선택하면 요소 1은 색인 2로 내려갑니다. 홉핑을 선택하면 결과 배열은 [5 1 3 4 6]. 엘리먼트 3은 이제 1 또는 2 이상의 위치를 건너 뛰고 프로세스가 반복됩니다. 한 위치에서 3 홉 이상 올리면 배열이 [5 3 1 4 6]이되고 두 위치에서 홉을 잡으면 이제 [3 5 1 4 6]이됩니다.소스와 최종 배열이 주어지면 2 차 시간 복잡도보다 작은 소스에서 최종 생성 할 홉 수를 찾습니다.
요소의 모든 가능한 순열이 이런 식으로 가능하다는 것을 보여주는 것은 매우 쉽습니다. 또한 최종 구성에는 고유 한 발생 세트가 있습니다.
최종 배열과 소스 배열이 주어지면 소스에서 최종 배열에 도달하는 데 필요한 총 홉 수를 찾습니다. O (N^2) 구현은 쉽게 찾을 수 있지만 O (N) 또는 O (NlogN)에서 수행 할 수 있다고 생각합니다. 또한 O (N2)보다 더 잘 할 수 없다면 알아두면 좋습니다. 마지막 배열 [3,5,1,4,6 들면
이면 소스 배열 [1,5,3,4,6 같이, 응답은 3
내 O 것 (N2) 알고리즘은 다음과 같습니다. 마지막으로 소스 배열의 모든 위치를 루프합니다. 이동하는 마지막 요소임을 알고 있기 때문입니다. 여기서는 6이 될 것이며 최종 배열에서 위치를 확인합니다. 우리는 필요한 홉 수를 계산하고 소스 배열의 원래 위치에 해당 요소를 배치하기 위해 최종 배열을 다시 정렬해야합니다. 재 배열 단계는 배열의 모든 요소를 처리하고 모든 요소에 대해 프로세스를 반복하므로 O (N^2)입니다. 해시 맵이나지도를 사용하면 검색에 도움이 될 수 있지만 O (N^2) 단계에서 매 단계마다지도를 업데이트해야합니다.
P. 나는 베이지안 방식으로 2 개의 순열 사이의 상관 관계를 모델링하려고 노력하고 있는데, 이것은 이것의 하위 문제이다. 생성 프로세스를 수정하여 문제를 간단하게 만드는 방법에 대한 아이디어도 도움이됩니다.
편집 : 내 대답을 찾았습니다. 이것은 Kendall Tau 거리가하는 것과 정확히 같습니다. 이것을 O (NlogN)에서 찾아내는 쉬운 병합 정렬 기반 알고리즘이 있습니다.
O (N^2) 알고리즘은 무엇입니까? – v78
왜 "대답은 3이 될까요?" 여기에 2 홉이 있습니다 - 3 홉에서 1 위까지 그리고 5 홉에서 2까지. 또한 배열의 정수가 고유한지 아닌지를 가정 할 수 있습니까? –
@AlexanderAnikin 당신은 당신의 오른쪽이 아닌 당신의 왼쪽으로 갈 수 있습니다. 3이 가장 왼쪽에 있으므로 유효한 홉이 없습니다. 5를 사용하여 위치를 3과 바꾸면 [5,3,1,4,6]에 현재 홉 수가 1이됩니다. 그런 다음 요소 1이 왼쪽으로 두 칸을 두드려 현재 배열 [1,5,3,4 , 6]. 4와 6은 이미 원하는 위치에 있습니다. 따라서 총 홉 수는 3이됩니다. –