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) -> это делается из-за левых поворотов, чтобы убедиться, что мы не переходим в отрицательный индекс, а поворачиваем его до конца массива. Без него для массива с длиной 10 для индекса 0 и вращения -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 -> вторая нормализация гарантирует, что новое значение индекса не выходит за пределы массива, но вращает значение в начале массива. Это для правильных вращений, так как в массиве с длиной 10 без него для индекса 9 и вращением 1 мы бы вошли в индекс 10, который находится вне массива, а не для того, чтобы значение реального вращения было равно 0. ((9 + 10 + (1% 10))% 10 = 0)