Как эффективно вращать массив?

Question

Учитывая массив чисел n и число, d, выполните левые вращения по массиву. Затем распечатайте обновленный массив как одну строку целых чисел, разделенных пробелами.

Пример ввода:

5 4

1 2 3 4 5

Образец Выход: 5 1 2 3 4

Первая строка содержит два целых числа через пробел, обозначающих соответствующие значения n (количество целых чисел) и d (количество левых поворотов, которое вы должны выполнить). Вторая строка содержит n целые числа, разделенные пробелами, описывающие соответствующие элементы начального состояния массива.

static void Main(String[] args) 
{ 
    string[] arr_temp = Console.ReadLine().Split(' '); 
    int n = Int32.Parse(arr_temp[0]); 
    int d = Int32.Parse(arr_temp[1]); 

    string[] arr = Console.ReadLine().Split(' '); 
    string[] ans = new string[n]; 

    for (int i = 0; i < n; ++i) 
    { 
     ans[(i + n - d) % n] = arr[i]; 
    } 

    for (int j = 0; j < n; ++j) 
    { 
     Console.Write(ans[j] + " "); 
    } 
} 

Как использовать меньше памяти для решения этой проблемы?

Answer 1

В большинстве случаев это будет использовать меньше памяти, так как второй массив будет только большим, чем сдвиг.

public static void Main(string[] args) 
{ 
    int[] n = { 1, 2, 3, 4, 5 }; 
    LeftShiftArray(n, 4); 
    Console.WriteLine(String.Join(",", n)); 
} 

public static void LeftShiftArray<T>(T[] arr, int shift) 
{ 
    shift = shift % arr.Length; 
    T[] buffer = new T[shift]; 
    Array.Copy(arr, buffer, shift); 
    Array.Copy(arr, shift, arr, 0, arr.Length - shift); 
    Array.Copy(buffer, 0, arr, arr.Length - shift, shift); 
} 

Answer 2

На самом деле вы спросили 2 вопроса:

Как эффективно вращать массив?

и

Как использовать меньше памяти, чтобы решить эту проблему?

Обычно эффективность и низкое использование памяти являются взаимоисключающими. Поэтому я отвечу на ваш второй вопрос, по-прежнему предоставляя наиболее эффективную реализацию в соответствии с этим ограничением памяти.

Следующий метод может использоваться как для левого (проходящего отрицательного счета), так и для правого (проходящего положительного отсчета) вращения. Он использует O (1) пространство (один элемент) и O (n * min (d, n - d)) операции копирования элементов массива (O (мин (d, n - d)) массив блок копия операции). В худшем случае он выполняет O (n/2) операции копирования блока.

Алгоритм использует тот факт, что

rotate_left (п, д) == rotate_right (п, п - д)

Вот оно:

public static class Algorithms 
{ 
    public static void Rotate<T>(this T[] array, int count) 
    { 
     if (array == null || array.Length < 2) return; 
     count %= array.Length; 
     if (count == 0) return; 
     int left = count < 0 ? -count : array.Length + count; 
     int right = count > 0 ? count : array.Length - count; 
     if (left <= right) 
     { 
      for (int i = 0; i < left; i++) 
      { 
       var temp = array[0]; 
       Array.Copy(array, 1, array, 0, array.Length - 1); 
       array[array.Length - 1] = temp; 
      } 
     } 
     else 
     { 
      for (int i = 0; i < right; i++) 
      { 
       var temp = array[array.Length - 1]; 
       Array.Copy(array, 0, array, 1, array.Length - 1); 
       array[0] = temp; 
      } 
     } 
    } 
} 

Пример использования, например, в вашем примере:

var array = Enumerable.Range(1, 5).ToArray(); // { 1, 2, 3, 4, 5 } 
array.Rotate(-4); // { 5, 1, 2, 3, 4 } 

Answer 3

Вам действительно нужно физически перемещать что-нибудь? Если нет, вы можете просто сместить индекс.

Answer 4

Я также попытался это и ниже мой подход ... Спасибо

public static int[] RotationOfArray(int[] A, int k) 
    { 
     if (A == null || A.Length==0) 
      return null; 
     int[] result =new int[A.Length]; 
     int arrayLength=A.Length; 
     int moveBy = k % arrayLength; 
     for (int i = 0; i < arrayLength; i++) 
     { 
      int tmp = i + moveBy; 
      if (tmp > arrayLength-1) 
      { 
       tmp = + (tmp - arrayLength); 
      } 
      result[tmp] = A[i];    
     }   
     return result; 
    } 

Answer 5

Скажем, если у меня есть массив целочисленных 'ARR. Для поворота массива «n» вы можете сделать следующее:

static int[] leftRotation(int[] Arr, int n) 
{ 
    int tempVariable = 0; 
    Queue<int> TempQueue = new Queue<int>(a); 
     for(int i=1;i<=d;i++) 
     { 
      tempVariable = TempQueue.Dequeue(); 
      TempQueue.Enqueue(t); 
    } 

    return TempQueue.ToArray();` 
} 

Сообщите мне, если у вас есть замечания. Благодаря!