C# Language
O (n) Algoritme voor circulaire rotatie van een array
Zoeken…
Invoering
Op mijn pad naar het bestuderen van programmeren waren er eenvoudige, maar interessante problemen om op te lossen als oefeningen. Een van die problemen was om een array (of een andere verzameling) met een bepaalde waarde te roteren. Hier zal ik met u een eenvoudige formule delen om het te doen.
Voorbeeld van een generieke methode die een array roteert met een gegeven shift
Ik wil erop wijzen dat we naar links roteren wanneer de verschuivingswaarde negatief is en we naar rechts roteren wanneer de waarde positief is.
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;
}
Het ding dat belangrijk is in deze code is de formule waarmee we de nieuwe indexwaarde vinden na de rotatie.
(index + array.Length + shiftCount% array.Length)% array.Length
Hier is iets meer informatie over:
(shiftCount% array.Length) -> we normaliseren de verschuivingswaarde zodat deze zich in de lengte van de array bevindt (omdat in een array met lengte 10 verschuiving 1 of 11 hetzelfde is, geldt hetzelfde voor -1 en -11) .
array.Length + (shiftCount% array.Length) -> dit gebeurt door rotaties naar links om ervoor te zorgen dat we niet naar een negatieve index gaan, maar deze naar het einde van de array draaien. Zonder een array met lengte 10 voor index 0 en een rotatie -1 zouden we naar een negatief getal (-1) gaan en niet de echte rotatie-indexwaarde krijgen, die 9 is. (10 + (-1% 10) = 9)
index + array.Length + (shiftCount% array.Length) -> niet veel te zeggen hier, omdat we de rotatie op de index toepassen om de nieuwe index te krijgen. (0 + 10 + (-1% 10) = 9)
index + array.Length + (shiftCount% array.Length)% array.Length -> de tweede normalisatie zorgt ervoor dat de nieuwe indexwaarde niet buiten de array komt, maar roteert de waarde aan het begin van de array. Het is voor juiste rotaties, omdat in een array met lengte 10 zonder index 9 en een rotatie 1 we in index 10 zouden gaan, die buiten de array valt, en niet de echte rotatie-indexwaarde krijgen 0. ((9 + 10 + (1% 10))% 10 = 0)
