Modèles de résolution de problèmes

Bienvenue dans notre série de blogs sur la résolution de problèmes dans le génie logiciel moderne !

Dans la première partie, nous avons exploré le Modèle de compteur de fréquence, une technique puissante pour optimiser les algorithmes en comptant efficacement la fréquence des éléments. Si vous l'avez manqué ou si vous souhaitez un rappel rapide, n'hésitez pas à le consulter avant de continuer.

Dans cette partie, nous allons plonger dans un autre modèle essentiel : le modèle Multipointer. Ce modèle est inestimable lorsqu'il s'agit de scénarios dans lesquels plusieurs éléments doivent être comparés, recherchés ou parcourus simultanément. Explorons comment cela fonctionne et où vous pouvez l'appliquer pour améliorer l'efficacité de votre code.

02. Modèle multipointeur

Le modèle multipointeur est une technique utilisée dans la conception d'algorithmes où plusieurs pointeurs (ou itérateurs) sont utilisés pour parcourir des structures de données telles que des tableaux ou des listes chaînées. Au lieu de s'appuyer sur un seul pointeur ou une seule boucle, ce modèle utilise deux ou plusieurs pointeurs qui se déplacent dans les données à des vitesses différentes ou à partir de différents points de départ.

Exemple de problème

Écrivez une fonction appelée sumZero qui accepte un tableau trié d'entiers. La fonction doit trouver la première paire où la somme est nulle. Si une telle paire existe, renvoie un tableau qui inclut les deux valeurs ; sinon, retournez undefined.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Solution de base

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

Complexité temporelle - O(N^2)

Solution utilisant un modèle multipointeur

étape 1 : Comprendre le problème
Nous devons trouver deux nombres dans un tableau **sorted dont la somme donne zéro. Puisque le tableau est trié, nous pouvons profiter de cet ordre pour trouver la solution plus efficacement.

étape 2 : initialiser deux pointeurs
Configurez deux pointeurs : l'un (gauche) commençant au début du tableau et l'autre (droite) commençant à la fin.

Exemple :

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

Étape 3 : Calculer la somme des valeurs aux pointeurs
Additionnez les valeurs aux pointeurs gauche et droit pour obtenir la somme

Sum = -4 + 5 = 1

Étape 4 : Comparez la somme avec zéro

• Si la somme est supérieure à zéro : Déplacez le pointeur droit d'un pas vers la gauche pour diminuer la somme.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Si la somme est inférieure à zéro : Déplacez le pointeur gauche d'un pas vers la droite pour augmenter la somme.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

Étape 5 : Répétez le processus
Continuez à déplacer les pointeurs et à calculer la somme jusqu'à ce qu'ils se rencontrent ou qu'une paire soit trouvée.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

La somme est nulle, donc la fonction renvoie [-2, 2].

Si la boucle se termine sans trouver une telle paire, retournez undéfini.

Code final

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

REMARQUE :
Complexité temporelle : O(n) – La fonction est efficace et évolue linéairement avec la taille du tableau.
Complexité spatiale : O(1) – La fonction utilise une quantité minimale de mémoire supplémentaire.

Conclusion

Le modèle multipointeur est une technique puissante pour résoudre des problèmes impliquant la recherche, la comparaison ou la manipulation d'éléments dans une structure de données triée. En utilisant plusieurs pointeurs qui se rapprochent, nous pouvons améliorer considérablement l’efficacité des algorithmes, réduisant ainsi la complexité temporelle de O(n²) à O(n) dans de nombreux cas. Ce modèle est polyvalent et peut être appliqué à un large éventail de problèmes, ce qui en fait une stratégie essentielle pour optimiser les performances de votre code.

Restez à l'écoute de notre prochain article, où nous plongerons dans le Modèle de fenêtre coulissante, un autre outil essentiel pour résoudre les problèmes impliquant des segments de données dynamiques. C'est un modèle incroyablement utile qui peut vous aider à résoudre facilement des défis encore plus complexes !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!