Überprüfen Sie, ob N und sein Double existieren

1346. Überprüfen Sie, ob N und sein Double existieren

Schwierigkeit:Einfach

Themen: Array, Hash-Tabelle, Zwei Zeiger, Binäre Suche, Sortieren

Überprüfen Sie bei einem gegebenen Array arr aus ganzen Zahlen, ob zwei Indizes i und j vorhanden sind, so dass:

• i != j
• 0 <= i, j < arr.länge
• arr[i] == 2 * arr[j]

Beispiel 1:

• Eingabe: arr = [10,2,5,3]
• Ausgabe:wahr
• Erklärung: Für i = 0 und j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Beispiel 2:

• Eingabe: arr = [3,1,7,11]
• Ausgabe:false
• Erklärung: Es gibt kein i und j, das die Bedingungen erfüllt.

Einschränkungen:

• 2 <= arr.length <= 500
• -10³ <= arr[i] <= 10³

Hinweis:

1. Schleife von i = 0 bis arr.length und behält in einer Hashtabelle die Array-Elemente von [0, i - 1] bei.
2. Überprüfen Sie bei jedem Schritt der Schleife, ob wir das Element 2 * arr[i] bisher gesehen haben.
3. Überprüfen Sie auch, ob wir arr[i] / 2 gesehen haben, falls arr[i] % 2 == 0.

Lösung:

Wir können eine Hash-Tabelle (assoziatives Array) verwenden, um die Elemente zu verfolgen, auf die wir beim Durchlaufen des Arrays bereits gestoßen sind. Die Idee besteht darin, für jedes Element arr[i] zu prüfen, ob sein Double (d. h. 2 * arr[i]) oder seine Hälfte (d. h. arr[i] / 2, wenn es eine gerade Zahl ist) bereits angetroffen wurde.

Hier ist eine Schritt-für-Schritt-Lösung:

Planen:

1. Durchlaufen Sie das Array.
2. Überprüfen Sie für jedes Element arr[i], ob wir 2 * arr[i] oder arr[i] / 2 (wenn arr[i] gerade ist) in der Hash-Tabelle gesehen haben.
3. Wenn eine Bedingung erfüllt ist, wird „true“ zurückgegeben.
4. Andernfalls fügen Sie arr[i] zur Hash-Tabelle hinzu und fahren mit dem nächsten Element fort.
5. Wenn am Ende keine Übereinstimmung gefunden wird, geben Sie false zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 1346. Überprüfen Sie, ob N und sein Double existieren

  
  
  Erläuterung:




Hash-Tabelle: Wir verwenden das assoziative Array $hashTable, um die Elemente zu speichern, auf die wir bisher gestoßen sind.

Erste Bedingung: Für jedes Element arr[i] prüfen wir, ob arr[i] * 2 in der Hash-Tabelle vorhanden ist.

Zweite Bedingung: Wenn das Element gerade ist, prüfen wir, ob arr[i] / 2 in der Hash-Tabelle vorhanden ist.

Hinzufügen zur Hash-Tabelle: Nach der Überprüfung fügen wir arr[i] zur späteren Referenz zur Hash-Tabelle hinzu.

Return: Wenn wir eine Übereinstimmung finden, geben wir sofort true zurück. Wenn nach der Schleife keine Übereinstimmung gefunden wird, geben wir false zurück.



  
  
  Zeitkomplexität:



Die zeitliche Komplexität beträgt O(n), wobei n die Länge des Arrays ist. Dies liegt daran, dass jedes Element einmal verarbeitet wird und das Überprüfen oder Hinzufügen von Elementen in der Hash-Tabelle im Durchschnitt eine konstante Zeit in Anspruch nimmt.



  
  
  Raumkomplexität:



Die Platzkomplexität beträgt O(n) aufgrund des für die Hash-Tabelle erforderlichen Speichers.


Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
        
Das obige ist der detaillierte Inhalt vonÜberprüfen Sie, ob N und sein Double existieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!