将数组元素向左移动对于大输入而言超时

Question

这是HackerRank问题描述：对大小为n的数组的左旋转操作将数组元素d的每个元素向左移动。例如，如果对数组[1,2,3,4,5]进行左旋转，则该数组将变为[3,4,5,1,2]。

这是我的职能：

function leftRotation(arr, d) {
    let newArr = [];
    while (d > 0) {
        let first = arr.shift();
        newArr.push(first);
        d--;
    }
    return [...arr,...newArr];
}

console.log(leftRotation([1,2,3,4,5], 2))

但是它不能通过大型测试用例，例如n = 73000，d = 60000，

预先感谢您的任何想法。

Answer 1

请勿旋转N次。移位N % (length of array)次，因为假设您有一个5个项目的数组，并且要求将其移位5次，那么您基本上不必移位一次。

Start : [1, 2, 3, 4, 5]
1: [2, 3, 4, 5, 1]
2: [3, 4, 5, 1, 2]
3: [4, 5, 1, 2, 3]
4: [5, 1, 2, 3, 4]
5: [1, 2, 3, 4, 5]

编辑：

您可以使用类似的逻辑来优化代码，而不是优化数组中的actually shifting元素。例如：如果是N = 73000, D = 60000，则可以将数组splice乘以73000 % 60000，然后仅将返回的拼接数组附加到现有数组中并返回它。

Answer 2

• 对于数组arr，方法shift()的时间复杂度为O(arr.length)。
• 如果d大于n，则仍将执行shift() d次。
• 总计，您的时间复杂度可能上升到O(d * arr.length)，肯定太长。

但是，此问题可以在O(arr.length)时空中解决。如果您知道d，则可以轻松地将每个项目向左移d个位置。例如，arr.length = 5和d = 2

position:        0 1 2 3 4
     arr:        4 3 5 1 6              

position in arr: 2 3 4 0 1  
shifted_arr:     5 1 6 4 3                

因此，实际上，移位数组中位置i处的每个项目都对应于原始数组(i + d) % arr.length中位置arr处的一个项目。因此，代码如下所示：

function leftShift(arr, d) {
    let newArr = [];
    let size = arr.length;
    
    for (var i = 0; i < size; i++) {
        newArr.push(arr[(i + d) % size]);
    }
    
    return newArr;
}

console.log(leftShift([4, 3, 5, 1, 6], 2))

Answer 3

我不完全确定此方法的性能，但是可以在一行中完成。

function leftRotation(arr, d) {
    return [ ...arr.slice(d), ...arr.slice(0, d) ];
}

console.log(leftRotation([1, 2, 3, 4, 5], 2));