Algorithmusgymnastik 4

Find the Smallest Common Number Aus den drei ganzzahligen Arrays, die in aufsteigender Reihenfolge sortiert sind, müssen Sie die kleinste Zahl finden, die allen drei Arrays gemeinsam ist.

Erläuterung

Implementieren Sie bei drei ganzzahligen Arrays, die in ** aufsteigender Reihenfolge ** sortiert sind, einen Algorithmus, der die kleinste Zahl findet, die allen drei Arrays gemeinsam ist.

Schauen wir uns die folgenden drei Sequenzen an. Die Lösung ist ** 6 **, die Mindestanzahl, die allen Arrays gemeinsam ist.

Tipps

1. Nutzen Sie aufsteigende Sequenzen.
2. Verwenden Sie drei Zeiger.

Solution Runtime Complexity O(n)

Memory Complexity O(1)

Kommentar

Überlegen Sie, wie Sie die Tatsache nutzen können, dass Arrays in aufsteigender Reihenfolge sortiert sind.

Scannen Sie jedes Array mit drei Iteratoren (Iteratoren) gleichzeitig. Sie können beginnen, indem Sie das Array ab dem 0. Index scannen, der den Mindestwert für jedes Array enthält.

Wenn die Werte der Array-Indizes, auf die die drei Iteratoren zeigen, gleich sind Gibt den Mindestwert zurück, der in allen Arrays vorhanden ist (da die Arrays in aufsteigender Reihenfolge sortiert sind).

Überprüfen Sie andernfalls den Iterator, der auf den kleinsten der drei Punkte zeigt Der Iterator wird erhöht, um auf den nächsten Index zu verweisen.

Gibt Null zurück, wenn keine gemeinsame Nummer gefunden wird, wenn einer der drei Iteratoren das Ende des Arrays erreicht.

Implementierung

Test

Output