如何有效地旋转数组

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] + " ");
    }
}

在大多数情况下，

这将使用更少的内存，因为第二个数组仅与移位一样大。

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);
}

这个问题可能会有点棘手，但如果熟悉队列和堆栈，也有一个简单的解决方案。我所要做的就是定义一个队列(将包含给定的数组(和一个堆栈。接下来，我只需要将已取消排队的索引推送到堆栈，并将弹出的索引排入队列中的队列，最后返回队列。听起来令人困惑？检查下面的代码：

static int[] rotLeft(int[] a, int d) {
    Queue<int> queue = new Queue<int>(a);
    Stack<int> stack = new Stack<int>();
    while(d > 0)
    {
        stack.Push(queue.Dequeue());
        queue.Enqueue(stack.Pop());
        d--;            
    }
    return queue.ToArray();
}

你真的需要物理移动任何东西吗？如果没有，您可以改为移动索引。

实际上你问了两个问题：

如何有效地旋转数组？

和

如何使用更少的内存来解决这个问题？

通常，效率和低内存使用率是相互排斥的。因此，我将回答您的第二个问题，在该内存约束下仍然提供最有效的实现。

以下方法可用于左(通过负计数(或右(传递正计数(旋转。它使用 O(1( 空间(单元素(和 O(n * min(d， n - d(( 数组元素复制操作(O(min(d， n - d(( 数组块复制操作(。在最坏的情况下，它执行 O(n/2( 块复制操作。

该算法正在利用以下事实：

rotate_left(n， d( == rotate_right(n， n - d(

在这里：

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 } 

使用 IEnumerables 不是更好吗？因为它不会执行所有这些数学运算，不会分配那么多数组等

public static int[] Rotate(int[] elements, int numberOfRotations)
{
    IEnumerable<int> newEnd = elements.Take(numberOfRotations);
    IEnumerable<int> newBegin = elements.Skip(numberOfRotations);
    return newBegin.Union(newEnd).ToArray();
}

如果您实际上不需要返回数组，您甚至可以删除 .ToArray(( 并返回一个 IEnumerable

用法：

void Main()
{
    int[] n = { 1, 2, 3, 4, 5 };
    int d = 4;
    int[] rotated = Rotate(n,d);
    Console.WriteLine(String.Join(" ", rotated));
}

我也

试过这个，下面是我的方法......谢谢

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;
  }

我尝试在 C# 中使用堆栈和队列来实现输出，如下所示：

public int[] rotateArray(int[] A, int rotate)
{
    Queue<int> q = new Queue<int>(A);
    Stack<int> s;
    while (rotate > 0)
    {
        s = new Stack<int>(q);
        int x = s.Pop();
        s = new Stack<int>(s);
        s.Push(x);
        q = new Queue<int>(s);
        rotate--;
    }
    return q.ToArray();
}

我通过以下代码解决了 Hackerrank 的挑战。希望对您有所帮助。

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace ConsoleApp1
{
class ArrayLeftRotationSolver
{
    TextWriter mTextWriter;
    public ArrayLeftRotationSolver()
    {
         mTextWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
    }
    public void Solve()
    {
        string[] nd = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nd[0]);
        int d = Convert.ToInt32(nd[1]);
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp))
        ;
        int[] result = rotLeft(a, d);
        mTextWriter.WriteLine(string.Join(" ", result));
        mTextWriter.Flush();
        mTextWriter.Close();
    }
    private int[] rotLeft(int[] arr, int shift)
    {
        int n = arr.Length;
        shift %= n;
        int[] vec = new int[n];
        for (int i = 0; i < n; i++)
        {
            vec[(n + i - shift) % n] = arr[i];
        }
        return vec;
    }
    static void Main(string[] args)
    {
         ArrayLeftRotationSolver solver = new ArrayLeftRotationSolver();
         solver.Solve();
    }
}

}

希望这有帮助。

public static int[] leftrotation(int[] arr, int d)
    {
        int[] newarr = new int[arr.Length];
        var n = arr.Length;
        bool isswapped = false;
        for (int i = 0; i < n; i++)
        {
            int index = Math.Abs((i) -d);
            if(index == 0)
            {
                isswapped = true;
            }
            if (!isswapped)
            {
                int finalindex = (n) - index;
                newarr[finalindex] = arr[i];
            }
            else
            {
                newarr[index] = arr[i];
            }
        }
        return newarr;
    }

将项目放在位置 0 并添加到末尾。 删除位置 0 处的项目。 重复 n 次。

List<int> iList = new List<int>(); 
    private void shift(int n)
    {
        for (int i = 0; i < n; i++)
        {
            iList.Add(iList[0]);
            iList.RemoveAt(0);
        }

    }

一个老问题，但我想我会添加一个可能的解决方案，只使用一个中间数组(如果包含 LINQ Take 表达式，实际上是 2 个(。 此代码向右而不是向左旋转，但仍然可能有用。

public static Int32[] ArrayRightRotation(Int32[] A, Int32 k)
    {
        if (A == null)
        {
            return A;
        }
        if (!A.Any())
        {
            return A;
        }
        if (k % A.Length == 0)
        {
            return A;
        }
        if (A.Length == 1)
        {
            return A;
        }
        if (A.Distinct().Count() == 1)
        {
            return A;
        }
        for (var i = 0; i < k; i++)
        {
            var intermediateArray = new List<Int32> {A.Last()};
            intermediateArray.AddRange(A.Take(A.Length - 1).ToList());
            A = intermediateArray.ToArray();
        }
        return A;
    }

O(1( 空间，O(n( 时间解

我认为从理论上讲，这是最佳的，因为它在每个内部循环中进行长度就地交换和 1 个临时变量交换。

但是，我怀疑O(d(空间解决方案在现实生活中会更快，因为代码分支较少(CPU命令管道重置较少(和缓存局部性(主要是顺序访问与d元素步骤(。

static int[] RotateInplaceLeft(int[] a, int d)
{
    var swapCount = 0;
    //get canonical/actual d    
    d = d % a.Length;
    if(d < 0) d += a.Length;
    if(d == 0) return a;
    for (var i = 0; swapCount < a.Length; i++) //we're done after a.Length swaps
    {
        var dstIdx = i; //we need this becasue of ~this: https://youtu.be/lJ3CD9M3nEQ?t=251 
        var first = a[i]; //save first element in this group
        for (var j = 0; j < a.Length; j++)
        {
            var srcIdx = (dstIdx + d) % a.Length;
            if(srcIdx == i)// circled around 
            {
                a[dstIdx] = first;
                swapCount++;
                break; //hence we're done with this group
            }
            a[dstIdx] = a[srcIdx];
            dstIdx = srcIdx;
            swapCount++;
        }
    }
    return a;
}

如果你看一下约束，你会发现 d <= n(旋转次数 <= 数组中的元素数(。正因为如此，这可以在 1 行中解决。

static int[] rotLeft(int[] a, int d)
{
    return a.Skip(d).Concat(a.Take(d)).ToArray();
}

    // using the same same array, and only one temp variable
    // shifting everything several times by one
    // works, simple, but slow
    public static int[] ArrayRotateLeftCyclical(int[] a, int shift)
    {
        var length = a.Length;
        for (int j = 0; j < shift; j++)
        {
            int t = a[0];
            for (int i = 0; i < length; i++)
            {
                if (i == length - 1)
                    a[i] = t;
                else
                    a[i] = a[i + 1];
            }
        }
        return a;
    }

这是 גלעד ברקן 在另一个问题中发布的技巧的就地Rotate实现。诀窍是：

示例，k = 3：

1234567

首先反转到位，分别由 n-k 划定的两个部分：

4321 765

现在反转整个数组：

5671234

我的实现，基于 Array.Reverse 方法：

/// <summary>
/// Rotate left for negative k. Rotate right for positive k.
/// </summary>
public static void Rotate<T>(T[] array, int k)
{
    ArgumentNullException.ThrowIfNull(array);
    k = k % array.Length;
    if (k < 0) k += array.Length;
    if (k == 0) return;
    Debug.Assert(k > 0);
    Debug.Assert(k < array.Length);
    Array.Reverse(array, 0, array.Length - k);
    Array.Reverse(array, array.Length - k, k);
    Array.Reverse(array);
}

现场演示。

输出：

Array: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Rotate(5)
Array: 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7
Rotate(-2)
Array: 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9

假设我有一个整数"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();`
}

如果有任何意见，请告诉我。谢谢！

这是我

的尝试。这很容易，但由于某种原因，它在大块数据上超时：

        int arrayLength = arr.Length;
        int tmpCell = 0;
        for (int rotation = 1; rotation <= d; rotation++)
        {
            for (int i = 0; i < arrayLength; i++)
            {
                if (arr[i] < arrayElementMinValue || arr[i] > arrayElementMaxValue)
                {
                    throw new ArgumentException($"Array element needs to be between {arrayElementMinValue} and {arrayElementMaxValue}");
                }
                if (i == 0)
                {
                    tmpCell = arr[0];
                    arr[0] = arr[1];
                }
                else if (i == arrayLength - 1)
                {
                    arr[arrayLength - 1] = tmpCell;
                }
                else
                {
                    arr[i] = arr[i + 1];
                }
            }
        }

这个呢？

 public static void RotateArrayAndPrint(int[] n, int rotate)
    {
         for (int i = 1; i <= n.Length; i++)
        {
            var arrIndex = (i + rotate) > n.Length ? n.Length - (i + rotate) : (i + rotate);
            arrIndex = arrIndex < 0 ? arrIndex * -1 : arrIndex;
            var output = n[arrIndex-1];
            Console.Write(output + " ");
        }
    }

这是一个非常简单的答案。最主要的是如何选择起始索引。

    public static List<int> rotateLeft(int d, List<int> arr) {
        int n = arr.Count;
        List<int> t = new List<int>();
        int h = d;
        for (int j = 0; j < n; j++)
        { 
            if ((j + d) % n == 0)
            {
                h = 0;
            }
           
            t.Add(arr[h]);
            h++;
        } 
        return t;
    }

使用这段代码，我已经成功提交到黑客排名问题，

    // fast and beautiful method
    // reusing the same array
    // using small temp array to store replaced values when unavoidable
    // a - array, s - shift 
    public static int[] ArrayRotateLeftWithSmallTempArray(int[] a, int s)
    {
        var l = a.Length;
        var t = new int[s]; // temp array with size s = shift
        for (int i = 0; i < l; i++)
        {
            // save cells which will be replaced by shift
            if (i < s)
                t[i] = a[i];
            if (i + s < l)
                a[i] = a[i + s];
            else
                a[i] = t[i + s - l];
        }
        return a;
    }

https://github.com/sam-klok/ArraysRotation

public static void Rotate(int[] arr, int steps)
    {
        for (int i = 0; i < steps; i++)
        {
            int previousValue = arr[arr.Length - 1];
            for (int j = 0; j < arr.Length; j++)
            {
                int currentValue = arr[j];
                arr[j] = previousValue;
                previousValue = currentValue;
            }
        }
    }