javascript - hackerrank 循环数组旋转由于 Javascript 超时而终止

Question

我陷入了 hackerrank 上的圆形数组旋转算法的困境，存在超时问题，并且无法提高其效率。

我正在使用 JavaScript:

  function processData(input) {
    var arr = new Array(4);
    var arrInt = [];
    var n, k, q, index, temp;

    arr = input.split(" ", 3); //input is a string, get n,k,q from this

    arrInt = input.split("\n");

    n = parseInt(arr[0]);
    k = parseInt(arr[1]);
    q = parseInt(arr[2]);

    var arrIntI = new Array(n);

    arrIntI = arrInt[1].match(/\d+/g); //read in integer array
    arrInt.shift();
    arrInt.shift();

   for(i = 0; i < k; i++){ //rotate array k times
        arrIntI.unshift(arrIntI.pop()); //Timeout on cases: 5, 9, 10, 12, 13, 14; passes all others!!!!!!

       //********************** Manual rotation: 
       //Timeout on cases: 5, 7, 9, 10, 12, 13, 14; Worse that Pop/unshift!!
       //temp = arrIntI[n-1];
       //for(l = n; l > 0; l--){
       //    arrIntI[l] = arrIntI[l - 1]; 
       //}
       //arrIntI[0] = temp;
       //delete arrIntI[n];
       //*******************************
    }    

    for(j = 0; j < q; j++){
        index = arrInt[j];
        console.log(arrIntI[index]);        
    }    

} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

我尝试用 for 循环替换 unshift/pop 来旋转数组，但它对超时情况没有帮助。

提前致谢!!

Answer 1

您根本不需要实际旋转数组，只需使用索引即可计算所有内容。

function int(v){ return v|0 }

function processData(input) {
    //parse input string
    var rows = input.split("\n");
    var values = rows[1].split(" ");
    var [n,k,q] = rows[0].split(" ").map( int );

    //a minimal validation of the input string
    if(values.length !== n || rows.length-2 !== q) 
        throw new Error("inconsistent imput");

    //compute a positive offset
    var offset = n - k%n;       
    //the requested indices start in row 3 (index 2)
    return rows.slice(2)
        //compute the offset positions, and return the particular values
        .map(m => values[ ( int(m) + offset )%n ])
        .join("\n")
}

编辑:抱歉，我解释得有点晚了。

首先，想象你有一个时钟(一个经典的圆形时钟，上面有指针)，然后你得到练习题:“将时钟上的数字向左旋转 5 小时，然后告诉我哪个数字在1、3、6 点钟位置？”
你是怎么做到的？您会开始拆卸时钟，然后将每个数字 1 的位置向左移动 5 次吗？
我敢打赌你根本不会碰这些数字，而只是对自己说:“向左旋转 5 小时，然后每个位置都显示所要求位置右侧的数字 5 索引”，当要求提供实际数字时例如，在特定索引处，您转到索引 3，添加 5 个索引，并告诉您在该位置读取的数字。

这就是它的工作原理。我只需添加所要求的索引和偏移量，然后返回该位置的值。

现在清楚这是如何工作的了吗？