Technique Java Two Pointer

1. Vue d'ensemble

Dans ce didacticiel, nous discuterons de l'approche à deux pointeurs pour résoudre les problèmes impliquant des tableaux et des listes. Cette technique est un moyen simple et efficace d'améliorer les performances de notre algorithme.

2. Description de la technique

Dans de nombreux problèmes impliquant des tableaux ou des listes, nous devons analyser chaque élément du tableau par rapport à ses autres éléments.

Pour résoudre de tels problèmes, nous partons généralement du premier index et parcourons le tableau une ou plusieurs fois selon notre implémentation. Parfois, nous devons également créer un tableau temporaire en fonction des exigences de notre problème.

L'approche ci-dessus pourrait nous donner le résultat correct, mais elle ne nous donnera probablement pas la solution la plus efficace en termes d'espace et de temps.

En conséquence, il est souvent bon de se demander si notre problème peut être résolu efficacement en utilisant l' approche à deux points .

Dans l'approche à deux pointeurs, les pointeurs font référence aux index d'un tableau. En utilisant des pointeurs, nous pouvons traiter deux éléments par boucle, au lieu d'un seul.

Les modèles courants de l'approche à deux points impliquent:

  • Deux pointeurs chacun commençant par le début et la fin jusqu'à ce qu'ils se rencontrent tous les deux
  • Un pointeur se déplace à un rythme lent tandis que l'autre se déplace à un rythme plus rapide

Les deux modèles ci-dessus peuvent nous aider à réduire la complexité temporelle et spatiale de nos problèmes, car nous obtenons le résultat attendu en moins d'itérations et sans utiliser trop d'espace supplémentaire.

Maintenant, jetons un coup d'œil à quelques exemples qui nous aideront à mieux comprendre cette technique.

3. La somme existe dans un tableau

Problème: étant donné un tableau trié d'entiers, nous devons voir s'il contient deux nombres de sorte que leur somme soit égale à une valeur spécifique.

Par exemple, si notre tableau d'entrée est [1, 1, 2, 3, 4, 6, 8, 9] et que la valeur cible est 11 , alors notre méthode doit retourner true . Cependant, si la valeur cible est 20 , elle doit renvoyer false .

Voyons d'abord une solution naïve:

public boolean twoSumSlow(int[] input, int targetValue) { for (int i = 0; i < input.length; i++) { for (int j = 1; j < input.length; j++) { if (input[i] + input[j] == targetValue) { return true; } } } return false; }

Dans la solution ci-dessus, nous avons bouclé deux fois le tableau d'entrée pour obtenir toutes les combinaisons possibles. Nous avons vérifié la somme de la combinaison par rapport à la valeur cible et renvoyé true si elle correspond. La complexité temporelle de cette solution est O (n ^ 2) .

Voyons maintenant comment appliquer la technique à deux pointeurs ici:

public boolean twoSum(int[] input, int targetValue) { int pointerOne = 0; int pointerTwo = input.length - 1; while (pointerOne < pointerTwo) { int sum = input[pointerOne] + input[pointerTwo]; if (sum == targetValue) { return true; } else if (sum < targetValue) { pointerOne++; } else { pointerTwo--; } } return false; }

Puisque le tableau est déjà trié, nous pouvons utiliser deux pointeurs. Un pointeur commence au début du tableau et l'autre pointeur commence à la fin du tableau, puis nous ajoutons les valeurs à ces pointeurs. Si la somme des valeurs est inférieure à la valeur cible, nous incrémentons le pointeur gauche, et si la somme est supérieure à la valeur cible, nous décrémentons le pointeur droit.

Nous continuons à déplacer ces pointeurs jusqu'à ce que nous obtenions la somme qui correspond à la valeur cible ou que nous ayons atteint le milieu du tableau et qu'aucune combinaison n'ait été trouvée. La complexité temporelle de cette solution est O (n) et la complexité spatiale est O (1) , une amélioration significative par rapport à notre première implémentation.

4. Rotation de la matrice k étapes

Problème: Étant donné un tableau, faites pivoter le tableau vers la droite de k pas, où k est non négatif. Par exemple, si notre tableau d'entrée est [1, 2, 3, 4, 5, 6, 7] et k est 4 , alors la sortie doit être [4, 5, 6, 7, 1, 2, 3] .

Nous pouvons résoudre cela en ayant à nouveau deux boucles qui rendront la complexité temporelle O (n ^ 2) ou en utilisant un tableau temporaire supplémentaire, mais cela rendra la complexité spatiale O (n) .

Résolvons à la place en utilisant la technique à deux pointeurs:

public void rotate(int[] input, int step) { step %= input.length; reverse(input, 0, input.length - 1); reverse(input, 0, step - 1); reverse(input, step, input.length - 1); } private void reverse(int[] input, int start, int end) { while (start < end) { int temp = input[start]; input[start] = input[end]; input[end] = temp; start++; end--; } }

Dans les méthodes ci-dessus, nous inversons les sections du tableau d'entrée sur place, plusieurs fois, pour obtenir le résultat requis. Pour inverser les sections, nous avons utilisé l'approche à deux pointeurs où l'échange d'éléments était effectué aux deux extrémités de la section du tableau.

Plus précisément, nous inversons d'abord tous les éléments du tableau. Ensuite, nous inversons les k premiers éléments puis inversons le reste des éléments. La complexité temporelle de cette solution est O (n) et la complexité spatiale est O (1) .

5. Élément central dans une LinkedList

Problème: étant donné une seule LinkedList , trouvez son élément central. Par exemple, si notre entrée LinkedList est 1-> 2-> 3-> 4-> 5, alors la sortie doit être 3 .

Nous pouvons également utiliser la technique à deux pointeurs dans d'autres structures de données similaires à des tableaux comme une LinkedList :

public  T findMiddle(MyNode head) { MyNode slowPointer = head; MyNode fastPointer = head; while (fastPointer.next != null && fastPointer.next.next != null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }

Dans cette approche, nous parcourons la liste chaînée à l'aide de deux pointeurs. Un pointeur est incrémenté de un tandis que l'autre est incrémenté de deux. Lorsque le pointeur rapide atteint la fin, le pointeur lent se trouve au milieu de la liste liée. La complexité temporelle de cette solution est O (n) et la complexité spatiale est O (1) .

6. Conclusion

Dans cet article, nous avons expliqué comment appliquer la technique à deux pointeurs en consultant quelques exemples et en regardant comment elle améliore l'efficacité de notre algorithme.

Le code de cet article est disponible à l'adresse over sur Github.