4
votes

Supprimer les doublons adjacents sur la matrice

Supposons que nous ayons un tableau de nombres comme le suivant:

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Le but est de supprimer les doublons, mais seulement s'ils sont adjacents. Donc, la sortie attendue pour l'exemple précédent devrait être:

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1, 1, 1, 1];

const remAdjDups = ([x, y, ...rest], out = []) =>
{
    if (!rest.length)
        return (x === y) ? [...out, x] : [...out, x, y];
    else if (x === y)
        return remAdjDups([x, ...rest], out);
    else
        return remAdjDups([y, ...rest], [...out, x]);
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

Jusqu'à présent, j'ai presque réussi à résoudre ce problème en utilisant une approche récursive, mais pour une raison que je ne peux pas figure, le résultat généré n'est pas retourné (cependant, vous pouvez le voir dans le journal avant la condition de retour).

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const remAdjDups = (arr, output = []) =>
{
    if (!arr.length)
    {
        console.log("Result before return: ", output);
        return output;
    }

    if (arr[0] === arr[1])
    {
        arr.splice(1, 1);
        remAdjDups(arr, output);
    }
    else
    {
        remAdjDups(arr.slice(1), output.concat(arr[0]));
    }
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

Donc, d'abord et principalement , j'aimerai comprendre ce qui se passe avec mon approche, et ensuite je suis ouvert à toute autre approche ( de tout type) qui pourrait résoudre ce problème.

Solution mise à jour

Juste au cas où quelqu'un serait intéressé, j'ai finalement résolu ce problème en utilisant la récursivité de cette façon. Je sais que la solution de filtrage est courte et élégante, mais je m'entraînais à résoudre par récursivité.

[2, 0, 2, 3, 0, 1]

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

javascript arrays recursion

0 commentaires

5 Réponses :

4
votes

Concernant votre solution, ajoutez simplement return avant remAdjDups(arr...

J'ai utilisé Array.prototype.filter pour cela

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const result = input.filter((i,idx) => input[idx-1] !== i)

console.log(result)

4 commentaires

Ok, c'est une belle approche! Cependant, je suis principalement intéressé par les raisons pour lesquelles mon approche ne fonctionne pas.

@Shidersz J'ai déjà mis à jour ma réponse pour y répondre également (avant que vous n'écriviez votre commentaire)

Je ne peux pas croire que j'ai raté ça, je devrais supprimer la question, sinon parce que j'ai déjà voté sur vos réponses ...

@Shidersz nous arrive à tous! Pourquoi supprimer? Personne ne l'a signalé comme inapproprié ou en double. Par conséquent, vous devez choisir la meilleure réponse (probablement en considérant également celle qui est apparue plus tôt).

1
votes

Vous pouvez utiliser filtre a >

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const result = input.filter((i,index) => {
 if(index != 0){
  return input[index-1] !== i
 } 
 return i
})

console.log(result)

0 commentaires

1
votes

Votre approche est correcte, vous avez simplement oublié de renvoyer le résultat de l'appel récursif . Tout ce dont vous avez besoin est d'ajouter une instruction return .

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const remAdjDups = (arr, output = []) =>
{
    if (!arr.length)
    {
        console.log("Result before return: ", output);
        return output;
    }

    if (arr[0] === arr[1])
    {
        arr.splice(1, 1);
        return remAdjDups(arr, output);
    }
    else
    {
        return remAdjDups(arr.slice(1), output.concat(arr[0]));
    }
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

J'espère que cela vous aidera!

0 commentaires

1
votes

Vous devez utiliser return dans les blocs if et else de votre code, sinon undefined va être retourné.

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1, 1, 1, 6, 3, 3, 5, 8, 8, 0, -1, -1, 2, 56, 57, 56];

const arr = input.reduce((acc, ele, idx) => {
  if(ele !== input[idx + 1]){
   acc.push(ele)
  }
  return acc;
}, []);

console.log(arr);

Ceci est une autre approche utilisant Array # réduire

if (arr[0] === arr[1])
{
    arr.splice(1, 1);
    return remAdjDups(arr, output);
}
else
{
    return remAdjDups(arr.slice(1), output.concat(arr[0]));
}

0 commentaires

1
votes

La récursion par induction mathématique fonctionne bien pour ce problème -

Si le premier élément, a , est nul, renvoie le résultat vide
(induction) le premier élément n'est PAS nul. Si le deuxième élément, b , est nul, renvoie un tableau singleton du premier élément, a
(induction) ni le premier élément NI le deuxième élément ne sont nuls. Si a est égal à b , renvoyez le résultat récursif avec a supprimé
(récurrence) ni le premier élément ni le deuxième élément ne sont nuls et ils ne sont PAS égaux l'un à l'autre. Renvoie le résultat récursif sans supprimer ni a ni b

const removeDupes = ([ a, b, ...more ]) =>
  a == null
    ? []                                  // 1
: b == null
    ? [ a ]                               // 2
: a === b
    ? removeDupes([ b, ...more ])         // 3
: [ a, ...removeDupes([ b, ...more ]) ]   // 4

const input =
  [2, 2, 0, 2, 3, 3, 3, 0, 0, 1, 1];

const result =
  removeDupes(input)
  
console.log(result)
// [ 2, 0, 2, 3, 0, 1 ]

0 commentaires