Tecnica Java Two Pointer

1. Panoramica

In questo tutorial, discuteremo l'approccio a due puntatori per risolvere i problemi che coinvolgono array ed elenchi. Questa tecnica è un modo semplice ed efficiente per migliorare le prestazioni del nostro algoritmo.

2. Descrizione della tecnica

In molti problemi che coinvolgono array o elenchi, dobbiamo analizzare ogni elemento dell'array rispetto ai suoi altri elementi.

Per risolvere problemi come questi di solito partiamo dal primo indice e ripetiamo un ciclo attraverso l'array una o più volte a seconda della nostra implementazione. A volte, dobbiamo anche creare un array temporaneo a seconda dei requisiti del nostro problema.

L'approccio di cui sopra potrebbe darci il risultato corretto, ma probabilmente non ci darà la soluzione più efficiente in termini di spazio e tempo.

Di conseguenza, spesso è bene considerare se il nostro problema può essere risolto in modo efficiente utilizzando l' approccio a due punti .

Nell'approccio a due puntatori, i puntatori fanno riferimento agli indici di un array. Usando i puntatori, possiamo elaborare due elementi per ciclo, invece di uno solo.

I modelli comuni nell'approccio a due puntatori coinvolgono:

  • Due indicatori ciascuno che iniziano dall'inizio e dalla fine fino a quando entrambi si incontrano
  • Un puntatore si sposta a un ritmo lento mentre l'altro si sposta a un ritmo più veloce

Entrambi i modelli di cui sopra possono aiutarci a ridurre la complessità temporale e spaziale dei nostri problemi poiché otteniamo il risultato atteso in meno iterazioni e senza utilizzare troppo spazio aggiuntivo.

Diamo ora un'occhiata ad alcuni esempi che ci aiuteranno a capire un po 'meglio questa tecnica.

3. Sum esiste in un array

Problema: dato un array ordinato di numeri interi, dobbiamo vedere se ci sono due numeri in modo tale che la loro somma sia uguale a un valore specifico.

Ad esempio, se il nostro array di input è [1, 1, 2, 3, 4, 6, 8, 9] e il valore di destinazione è 11 , il nostro metodo dovrebbe restituire true . Tuttavia, se il valore di destinazione è 20 , dovrebbe restituire false .

Vediamo prima una soluzione ingenua:

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; }

Nella soluzione precedente, abbiamo ripetuto due volte l'array di input per ottenere tutte le possibili combinazioni. Abbiamo verificato la somma della combinazione rispetto al valore target e abbiamo restituito true se corrisponde. La complessità temporale di questa soluzione è O (n ^ 2) .

Ora vediamo come possiamo applicare la tecnica dei due puntatori qui:

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; }

Poiché l'array è già ordinato, possiamo usare due puntatori. Un puntatore inizia dall'inizio della matrice e l'altro dalla fine della matrice, quindi aggiungiamo i valori a questi puntatori. Se la somma dei valori è inferiore al valore di destinazione, incrementiamo il puntatore sinistro e se la somma è maggiore del valore di destinazione, diminuiamo il puntatore di destra.

Continuiamo a spostare questi puntatori fino a quando non otteniamo la somma che corrisponde al valore di destinazione o non abbiamo raggiunto la metà della matrice e non sono state trovate combinazioni. La complessità temporale di questa soluzione è O (n) e la complessità spaziale è O (1) , un miglioramento significativo rispetto alla nostra prima implementazione.

4. Ruota la matrice k passi

Problema: dato un array, ruotalo verso destra di k passi, dove k è non negativo. Ad esempio, se il nostro array di input è [1, 2, 3, 4, 5, 6, 7] e k è 4 , l'output dovrebbe essere [4, 5, 6, 7, 1, 2, 3] .

Possiamo risolvere questo problema avendo di nuovo due cicli che renderanno la complessità temporale O (n ^ 2) o usando un array temporaneo aggiuntivo, ma questo renderà la complessità spaziale O (n) .

Risolviamolo usando invece la tecnica dei due puntatori:

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--; } }

Nei metodi precedenti, invertiamo le sezioni della matrice di input sul posto, più volte, per ottenere il risultato richiesto. Per invertire le sezioni, abbiamo utilizzato l'approccio a due puntatori in cui lo scambio di elementi veniva eseguito su entrambe le estremità della sezione dell'array.

Nello specifico, prima invertiamo tutti gli elementi dell'array. Quindi, invertiamo i primi k elementi seguiti dall'inversione del resto degli elementi. La complessità temporale di questa soluzione è O (n) e la complessità spaziale è O (1) .

5. Elemento centrale in un LinkedList

Problema: dato un unico LinkedList , trova il suo elemento centrale. Ad esempio, se il nostro input LinkedList è 1-> 2-> 3-> 4-> 5, l'output dovrebbe essere 3 .

Possiamo anche usare la tecnica a due puntatori in altre strutture di dati simili agli array come una 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; }

In questo approccio, attraversiamo l'elenco collegato utilizzando due puntatori. Un puntatore viene incrementato di uno mentre l'altro viene incrementato di due. Quando il puntatore veloce raggiunge la fine, il puntatore lento sarà al centro dell'elenco collegato. La complessità temporale di questa soluzione è O (n) e la complessità spaziale è O (1) .

6. Conclusione

In questo articolo, abbiamo discusso di come possiamo applicare la tecnica dei due puntatori vedendo alcuni esempi e visto come migliora l'efficienza del nostro algoritmo.

Il codice in questo articolo è disponibile su Github.