[씨] o (n) 복잡도에서 설정된 위치 수만큼 배열을 왼쪽 또는 오른쪽으로 회전
Programming Pearls Column 2의 Jon Bentley는 가장 우아하고 효율적인 솔루션으로 알려진 것을 설명합니다.
회전 알고리즘은
reverse()
배열의 하위 시퀀스를 반대로 하는 함수 를 사용합니다 . 칼럼에서 인용 :문제를 배열
ab
을 배열 로 변환하는ba
것으로 보겠습니다.하지만 배열 의 지정된 부분에있는 요소를 반전시키는 함수가 있다고 가정 해 보겠습니다. ab로 시작하여 a를 뒤집어 a_r b를, b를 반대로 a_r b_r을 얻은 다음 모든 것을 뒤집어 (a_r b_r) _r을 얻습니다. 정확히 ba입니다.
이것이 당신이 필요로하는 것입니다. 사용자의 입력은 배열을 두 블록 A와 B로 분할 할 위치를 정의합니다. 다음은 제 구현입니다.
void reverse(int a[], int sz) {
int i, j;
for (i = 0, j = sz; i < j; i++, j--) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
void rotate(int array[], int size, int amt) {
if (amt < 0)
amt = size + amt;
reverse(array, size-amt-1);
reverse(array+size-amt, amt-1);
reverse(array, size-1);
}
나는 그것을 테스트했고 작동하고 있습니다. 또한 음의 회전이 처리되는 방식에 유의하십시오. size
요소 배열을 amt
왼쪽으로 (즉, 음수 값으로) 회전하는 size+amt
것은 오른쪽 으로 회전하는 것과 같습니다 .
우아한 코드를 즐기고 댓글에 크레딧을 포함하는 것을 잊지 마십시오 (물론 Jon Bentley에게).
-------------------오른쪽 회전 사용 :
temp[0]=a[0];
for(i=1;i<=n;i++)
{
temp[i%2]=a[(i*d)%n];
a[(i*d)%n]=temp[(i+1)%2];
}
왼쪽 회전 사용 :
temp[0]=a[0];
for(i=1;i<=n;i++)
{
temp[i%2]=a[(i*(n-d))%n];
a[(i*(n-d))%n]=temp[(i+1)%2];
}
여기서 a [n]은 배열이고 d는 회전하려는 위치의 수입니다.
-------------------요소 위치를 바꾸는 것입니다. 위치 1의 요소는 위치 6에 배치되고 그 반대의 경우도 마찬가지입니다. 마지막 부분을 다시 작성해야합니다. 두 가지 방법이 있습니다.
- 새 배열을 할당하고 값을 하나씩 복사하십시오.
- 하나의 값을 tmp에 저장하고 다른 값을 이동하십시오.
사소한 접근 방식은 회전하는 것이지만 그 이상을 살펴보면 배열 / 목록의 요소 위치를 변경하는 것은 어떨까요?
def circularArrayRotation(a, k):
k=k%len(a)
b=a[len(a)-k:len(a)]
#print(b)
a=b+a[0:len(a)-k]
print(a)
그건 오른쪽 회전, 왼쪽 회전은 그냥 뒤집기
b=a[k:len(a)] and a=b+a[0:k]
출처
https://stackoverflow.com/questions/22079960