In diesem Blogbeitrag untersuchen wir den Denkprozess hinter einer Lösung für eine mögliche Interviewfrage, auf die Sie als Softwareentwickler stoßen könnten:Wie findet man das erste doppelte Element in einem Array (Ganzzahlen, Zeichenfolgen oder andere).
Auch wenn dieses Problem etwas einfacher ist als etwas, dem Sie direkt in einem Vorstellungsgespräch begegnen werden, wird das Kernkonzept, das wir verwenden, um es zu lösen (und der Prozess, es zu entwickeln), später auf weitaus komplexere Probleme anwendbar sein ein.
Bereit? Auf geht's!
Stellen wir zunächst sicher, dass uns klar ist, was unsere imaginäre Eingabeaufforderung ist:
Wenn Sie eine Eingabeaufforderung wie diese sehen, kann es ein bisschen verwirrend sein, wenn man von minimalen Indizes spricht, aber das Problem ist eigentlich ganz einfach, wenn Sie es auf den Punkt bringen. Im Wesentlichen wird darum gebeten, durch das Array zu navigieren, und das allererste Mal, wenn ein doppeltes Element gefunden wird, ist das das zurückzugebende Element! Beschreiben durch minimalen Index ist einfach eine technischere Art, es auszudrücken, da das erste Duplikat an einem früheren/niedrigeren Index auftreten sollte im Array.
Als Beispiel verwenden wir dieses Array von Ganzzahlen:
2, 3 und 4 sind alle im Array dupliziert, aber 3 ist das erste Duplikat, das bei einem Index von arr[4] aufgeführt wird . Das wollen wir mit unserer Funktion zurückgeben!
Lassen Sie uns nun einen Denkprozess untersuchen, wie dies gelöst werden kann. Dies ist der Schlüsselaspekt dieses Problems, mehr noch als die Lösung selbst.
Wenn wir ein Problem wie dieses sehen, fragen Sie nach etwas, das Duplikate in einem Array betrifft , ob es darum geht, sie zu finden, zu eliminieren oder auf andere Weise, wir wissen, dass wir wahrscheinlich zwei Dinge brauchen werden:
- Eine Schleife, die das Array durchläuft.
- Eine Datenstruktur, die Werte für diese Schleife zum Vergleich enthält.
Der Prozess hier ist:Wir wissen, dass wir uns die meisten (oder möglicherweise alle) Elemente des gegebenen Arrays ansehen müssen – daher die for-Schleife – und wir brauchen etwas, um jeden dieser betrachteten Werte zu halten um zu überprüfen, ob wir sie schon gesehen haben oder nicht. Dies ist ein logischer Ansatz, der in einer großen Menge von Array-bezogenen Interviewfragen und Algorithmen auftaucht, daher ist es unglaublich wertvoll, sich damit vertraut zu machen.
Es gibt verschiedene Datenstrukturen, die wir verwenden können, um diese Werte zu halten, aber wenn wir die Laufzeitkomplexität im Auge behalten, sollten wir sie im Kontext von JavaScript auf eine Hash-Tabelle, ein Map- oder ein Set-Objekt beschränken.
Der Grund, warum wir hier einen der oben genannten verwenden, ist, dass wir jeden Wert des gegebenen Arrays bei jedem Durchlauf durch die Schleife mit der Menge der bereits gesehenen Elemente vergleichen – und nach einem Schlüssel oder Wert in einer Hash-Tabelle suchen ist eine konstante Zeitkomplexität, verglichen mit der Verwendung von etwas wie Array.includes() Funktion, die bei jedem Durchlauf eine weitere verschachtelte Iteration hinzufügt. In diesem Fall verwenden wir ein Set Objekt, da es für unser spezielles Szenario perfekt funktioniert.
Zeit, an der Programmierung unserer Lösung zu arbeiten!
Lassen Sie uns zunächst unsere Funktion deklarieren:
function firstDuplicate(arr) {
}
Lassen Sie uns nun unser Set-Objekt erstellen:
function firstDuplicate(arr) {
let elementSet = new Set();
}
Dieses Set-Objekt ermöglicht es uns, jedes Element aus dem gegebenen Array als eindeutigen Wert zu speichern und mit zwei Funktionen zu prüfen, ob es bereits einen Wert enthält:Set.add() und Set.has() .
Lassen Sie uns nun unsere Schleife durch das angegebene Array implementieren:
function firstDuplicate(arr) {
let elementSet = new Set();
for (let i = 0; i < arr.length; i++) {
}
}
Und schließlich setzen wir die Kernlogik unseres Algorithmus ein:
- Wir prüfen, ob das Set bereits das Element enthält, auf dem wir uns gerade in unserer Schleife befinden – wenn es existiert, haben wir unser erstes Duplikat gefunden! Wir geben diesen Wert zurück und fertig.
- Bevor wir diesen Meilenstein erreichen können, brauchen wir eine „else“-Anweisung für den Fall, dass das Element nicht ist in unserem Set noch, in diesem Fall fügen wir hinzu es zum Set und fahren Sie mit dem nächsten Element im Array fort.
function firstDuplicate(arr) {
let elementSet = new Set();
for (let i = 0; i < arr.length; i++) {
if (elementSet.has(arr[i])) return arr[i];
elementSet.add(arr[i]);
}
}
Nur noch ein letzter Schritt:unser Grenzfall, bei dem keine Duplikate im Array zu finden sind! Wir fügen das nach unserer Schleife hinzu, vorausgesetzt, dass sie beendet wurde, ohne einen doppelten Wert zurückzugeben:
function firstDuplicate(arr) {
let elementSet = new Set();
for (let i = 0; i < arr.length; i++) {
if (elementSet.has(arr[i])) return arr[i];
elementSet.add(arr[i]);
}
return "No duplicates here!";
}
Und wir sind fertig! Wir haben jetzt das Wissen, schnell nach dem ersten Duplikat in einem JavaScript-Array zu suchen und es zurückzugeben, unabhängig vom Datentyp. Diese Funktion gibt das erste Duplikat in einem Array aus ganzen Zahlen, einem Array aus Strings oder einem gemischten Array zurück.
Vielen Dank, dass Sie sich die Zeit genommen haben, dieses Tutorial zu lesen. Ich hoffe, es hat Ihnen gefallen und Sie haben etwas mehr über die Konzepte hinter diesem speziellen Algorithmus gelernt! Bleiben Sie dran für weitere Blogs in der gleichen Richtung, während ich daran arbeite, auch mein eigenes Verständnis zu vertiefen. :)