2
votes

Étant donné un tableau et un entier positif d, décalez efficacement le tableau de d à gauche

Voici la description du problème du HackerRank : Une opération de rotation vers la gauche sur un tableau de taille n décale chacun des éléments du tableau d unité vers la gauche. Par exemple, si des rotations à gauche sont effectuées sur le tableau [1,2,3,4,5], alors le tableau deviendrait [3,4,5,1,2].

Voici ma fonction: p >

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

mais il ne passe pas de grands cas de test. Par exemple, pour n = 73000 et d=60000.

Merci d'avance pour toute idée.

javascript algorithm optimization rotation shift

0 commentaires

3 Réponses :

0
votes

Ne tournez pas N nombre de fois. Décalez N% (longueur du tableau) fois, car disons que vous avez un tableau de 5 éléments et que vous êtes invité à le décaler 5 fois, vous n'avez essentiellement pas à le faire changer même une fois.

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]

EDIT:[

Vous pouvez utiliser une logique similaire pour optimiser le code au lieu de déplacer réellement les éléments dans le tableau. Par exemple: dans le cas de N = 73000, D = 60000 , vous pouvez épisser le tableau par 73000% 60000 puis simplement ajouter le fichier renvoyé tableau épissé au tableau existant et le renvoyer.

1 commentaires

Merci de votre aide. je l'ai essayé, cela ne fonctionne pas pour les grands cas de test

0
votes

Pour un tableau arr , une méthode shift () peut avoir une complexité temporelle de O (arr.length) .
Si d est supérieur à n , vous effectuez toujours shift () d fois.
Au total, votre complexité temporelle peut atteindre O (d * arr.length) , ce qui est certainement trop long.

Cependant, ce problème peut être résolu dans O (arr.length) temps et espace. Si vous connaissez d , vous pouvez facilement déplacer chaque élément de d positions vers la gauche. Par exemple, arr.length = 5 et d = 2

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

Donc en fait, chaque élément à la position i dans le tableau décalé correspond à un élément à la position (i + d)% arr.length dans le tableau d'origine arr . Par conséquent, le code peut se présenter comme suit:

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

0 commentaires

1
votes

Je ne suis pas entièrement sûr des performances de cette méthode, mais cela peut être fait en une seule ligne.

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

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

0 commentaires