C# Language
O (n) Algoritm för cirkulär rotation av en matris
Sök…
Introduktion
På min väg att studera programmering har det varit enkla, men intressanta problem att lösa som övningar. Ett av dessa problem var att rotera en matris (eller en annan samling) med ett visst värde. Här kommer jag att dela med dig en enkel formel för att göra det.
Exempel på en generisk metod som roterar en matris med en given skift
Jag vill påpeka att vi roterar åt vänster när växlingsvärdet är negativt och att vi roterar åt höger när värdet är positivt.
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;
}
Det som är viktigt i denna kod är formeln som vi hittar det nya indexvärdet efter rotationen.
(index + array.Length + shiftCount% array.Length)% array.Length
Här är lite mer information om det:
(shiftCount% array.Length) -> vi normaliserar växlingsvärdet för att vara i längden på arrayen (eftersom i en matris med längd 10, är shifting 1 eller 11 samma sak, detsamma gäller för -1 och -11) .
array.Length + (shiftCount% array.Length) -> detta görs på grund av vänsterrotationer för att se till att vi inte går in i ett negativt index, utan roterar det till slutet av arrayen. Utan det för en matris med längd 10 för index 0 och en rotation -1 skulle vi gå in i ett negativt tal (-1) och inte få det verkliga rotationsindexvärdet, som är 9. (10 + (-1% 10) = 9)
index + array.Length + (shiftCount% array.Length) -> inte mycket att säga här när vi tillämpar rotationen på indexet för att få det nya indexet. (0 + 10 + (-1% 10) = 9)
index + array.Length + (shiftCount% array.Length)% array.Length -> den andra normaliseringen är att se till att det nya indexvärdet inte går utanför matrisen utan roterar värdet i början av arrayen. Det är för höger rotationer, eftersom vi i en matris med längd 10 utan den för index 9 och en rotation 1 skulle gå in på index 10, som är utanför matrisen, och inte få det verkliga rotationsindexvärdet är 0. ((9 + 10 + (1% 10))% 10 = 0)