阵列旋转中的超时问题.这个解决方案有什么这么慢?

Question

我正在做一个关于Hackerrank的问题，这个问题应该将数组左移一定数量的旋转。 例如：

1 2 3 4 5 -> 2 3 4 5 1

单次旋转后。无论测试用例要求多少次，都会这样做。

这是我的代码：

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
string[] firstLine = Console.ReadLine().Split(' ');     
int numInts = Convert.ToInt32(firstLine[0]);               //Number of ints in list
int rotations = Convert.ToInt32(firstLine[1]);             //number of left rotations
int[] numList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);    //the list to rotate
for(int i = 0; i < rotations; i++){
int[] newArray = new int[numList.Length];
Array.Copy(numList, 1, newArray, 0, numList.Length-1);           //copy from index 1 to end
newArray[numList.Length-1] =  numList[0];               //end should equal first elem in old array
Array.Copy(newArray, numList, numList.Length);
}

foreach(var i in numList){
Console.Write(i + " ");
}
}
}

我通过了几乎所有测试，但在最后 2 次测试中遇到了超时问题。我想出的这个解决方案到底是什么这么慢？

如果您想了解更多信息，这里是问题的链接： https://www.hackerrank.com/challenges/array-left-rotation/problem

Answer 1

您应该意识到，如果您开始从索引 n 读取数组，则意味着它已被旋转了 n % 长度。考虑到这个推论，你的整个程序可以简化为

using System;
using System.Collections.Generic;
using System.IO;
class Solution 
{
static void Main(String[] args) 
{
string[] firstLine = Console.ReadLine().Split(' ');     
int numInts = Convert.ToInt32(firstLine[0]);               //Number of ints in list
int rotations = Convert.ToInt32(firstLine[1]);             //number of left rotations
int[] numList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);    //the list to rotate
for( var i = 0 ; i < numInts ; ++i )
Console.WriteLine( numList [ (i + rotations) % numInts ] );
}
}

Answer 2

数组的副本太多，这需要时间。我认为一开始的int.parse也是不需要的。您不应该在每次旋转后创建数组的副本，而是在最后一次旋转后计算每个元素的位置(计算多少步(

这是示例工作解决方案：

int rotations = 22222222;             //number of left rotations
string[] numList = "5 1 2 4 3".Split(' ');    //the list to rotate
var index = rotations % numInts;
var indexesToWrite = Enumerable.Range(index, numInts - index).Concat(Enumerable.Range(0, index));
foreach (var indexToWrite in indexesToWrite)
{
Console.Write(numList.ElementAt(indexToWrite) + " ");
}

为了澄清代码 - 很明显(正如其他人注意到的那样(，在我们旋转后的每个 [numInts] 时间，我们都会回到星形状态。因此，这显然使我们得出一个结论，即只有除法后的余数至关重要。之后，我们必须决定 % 运算符的结果是什么。实际上，这是从哪里开始(数组的索引("读取"numList数组的信息。到达表的末尾后，我们应该从 numList 数组的开头(index = 0(开始读取，直到我们开始读取的索引。

Answer 3

- Array a has n number of elements
- d variable used for number of left rotations

static int[] rotLeft(int[] a, int d) {
int l = a.Length, c = 0;
// if the array length is same as number of rotations not need to rotate the array. //we can return the same array as end result would be same
if( l == d)
return a;
// if array length is less the no of rotations, Here I am finding the reminder as //we can skip the l ( length of the array ) rotations as l rotations will give you the same array. //Now just rotate it to the new value d rotations to get the end result.              
if ( l < d) 
d = d % l;

int[] copy = new int[a.Length];
//In first loop I am copying values of array "a" from d to end of the array
for(int j=d; j< a.Length; j++)
{
copy[c] = a[j];
c++;
}
// Here I am appending the copy array values form 0 to start no of rotations
for(int i=0;i < d; i++ )
{
copy[c]= a[i];
c++;
}
// End result would be the result
return copy;
}