Блог

Это описание проблемы 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 .

Заранее спасибо за любую идею.

Я не совсем уверен в производительности этого метода, но это можно сделать в одной строке.

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

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

Не вращайте 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 , а затем просто добавить возвращенный объединенный массив к существующему массиву и вернуть его.

• Для массива 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))