C# Language
O (n) 배열의 원형 회전 알고리즘
수색…
소개
프로그래밍을 공부하는 제 길은 운동으로 해결할 수있는 간단하면서도 흥미로운 문제가있었습니다. 이러한 문제 중 하나는 배열 (또는 다른 컬렉션)을 특정 값만큼 회전하는 것이 었습니다. 여기서 나는 그걸 할 수있는 간단한 공식을 당신과 나눌 것입니다.
주어진 시프트만큼 배열을 회전시키는 일반적인 메소드의 예
나는 시프트 값이 음수 일 때 왼쪽으로 회전하고 값이 양수이면 우회전한다고 지적하고 싶습니다.
public static void Main()
{
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int shiftCount = 1;
Rotate(ref array, shiftCount);
Console.WriteLine(string.Join(", ", array));
// Output: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
array = new []{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
shiftCount = 15;
Rotate(ref array, shiftCount);
Console.WriteLine(string.Join(", ", array));
// Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]
array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
shiftCount = -1;
Rotate(ref array, shiftCount);
Console.WriteLine(string.Join(", ", array));
// Output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
shiftCount = -35;
Rotate(ref array, shiftCount);
Console.WriteLine(string.Join(", ", array));
// Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]
}
private static void Rotate<T>(ref T[] array, int shiftCount)
{
T[] backupArray= new T[array.Length];
for (int index = 0; index < array.Length; index++)
{
backupArray[(index + array.Length + shiftCount % array.Length) % array.Length] = array[index];
}
array = backupArray;
}
이 코드에서 중요한 것은 회전 후 새 인덱스 값을 찾는 수식입니다.
(index + array.Length + shiftCount % array.Length) % array.Length
그것에 대해 조금 더 많은 정보가 있습니다 :
(shiftCount % array.Length) -> 우리는 시프트 값을 배열의 길이로 정규화합니다 (길이 10 인 배열에서 1 또는 11의 시프 팅이 똑같고 -1과 -11에도 동일하게 적용됨) .
array.Length + (shiftCount % array.Length) -> 이것은 왼쪽 회전 때문에 수행됩니다. 우리는 음수 인덱스로 이동하지 않고 배열의 끝까지 회전시킵니다. 인덱스 0과 회전 -1에 대한 길이가 10 인 배열의 경우에는 -1이 아닌 -1로 이동하여 실제 회전 인덱스 값인 9를 얻지 못합니다. (10 + (-1 % 10) = 9)
index + array.Length + (shiftCount % array.Length) -> 새로운 인덱스를 얻기 위해 인덱스에 회전을 적용 할 때 여기서 말하기는별로하지 않습니다. (0 + 10 + (-1 % 10) = 9)
index + array.Length + (shiftCount % array.Length) % array.Length -> 두 번째 정규화는 새 인덱스 값이 배열 외부로 이동하지 않지만 배열 시작 부분의 값을 회전시킵니다. 그것은 올바른 회전을위한 것입니다. 왜냐하면 인덱스 9가없는 길이 10의 배열과 회전 1의 배열에서는 배열 외부에있는 인덱스 10에 들어가기 때문에 실제 회전 인덱스 값은 0이 아니기 때문입니다. ((9 + 10 + (1 % 10)) % 10 = 0)
