벡터의 순열

Question

벡터가 있다고 가정합니다.

 0  1  2  3  4  5
[45,89,22,31,23,76]

그리고 그 지수의 순열 :

[5,3,2,1,0,4]

순열에 따라이를 사용하는 효율적인 방법이 있습니까?

[76,31,22,89,45,23]

최대 o (1) 추가 공간 사용?

Answer 1

예. 가장 왼쪽 위치에서 시작하여 우리는 요소 올바른 위치 나는 그것을 그 위치에있는 (다른) 잘못 배치 된 요소로 바꾸어 i. 여기에서 O (1) 추가 공간이 필요한 곳입니다. 우리는이 위치의 요소가 올바르게 될 때까지 요소 쌍을 계속 교환합니다. 그래야만 우리는 다음 위치로 진행하고 같은 일을합니다.

예시:

5 3 2 1 0 4] 초기 상태

4 3 2 1 0 5] 교체 (5,4), 5는 이제 올바른 위치에 있지만 4는 여전히 틀 렸습니다.

0 3 2 1 4 5] 교체 (4,0), 이제 4와 0이 모두 올바른 위치에 있으며 다음 위치로 이동

0 1 2 3 4 5] 교체 (3,1), 이제 1과 3은 모두 올바른 위치에 있으며 다음 위치로 이동합니다.

0 1 2 3 4 5] 모든 요소는 올바른 위치에 있습니다.

메모:

각 스왑 작업은 적어도 두 개의 요소를 올바른 위치에두기 때문에 그러한 스왑이 모두 필요하지 않습니다.

Answer 2

Zach의 솔루션은 매우 좋습니다.

아직도, 나는 왜 분류가 필요한지 궁금했습니다. 지수의 순열이있는 경우 값을 이전 배열에 대한 포인터로 사용하십시오.

이렇게하면 배열을 처음에 정렬 할 필요가 없습니다. 이것은 모든 경우에 사용할 수있는 솔루션이 아니지만 대부분의 경우 잘 작동합니다.

예를 들어:

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

이제 값을 통해 lop을 원한다면 ㅏ, 당신은 (pseudo-code)와 같은 것을 할 수 있습니다.

for i=0 to 4
{
    process(a[i]);
}

새 순서의 값을 루프하려면 다음을 수행하십시오.

for i=0 to 4
{
    process(a[b[i]]);
}

앞에서 언급 한 바와 같이,이 용액은 많은 경우에 충분하지만 다른 경우에는 그렇지 않을 수 있습니다. 다른 경우 Zach의 솔루션을 사용할 수 있지만이 솔루션을 사용할 수있는 경우에는 정렬이 필요하지 않기 때문에 더 좋습니다.