Längster quadratischer Streifen in einem Array

2501. Längster quadratischer Streifen in einem Array

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Binäre Suche, Dynamische Programmierung, Sortierung

Sie erhalten ein ganzzahliges Array mit Zahlen. Eine Teilfolge von Zahlen wird als Quadratstreifen bezeichnet, wenn:

• Die Länge der Teilsequenz beträgt mindestens 2 und
• nach Sortieren der Teilfolge ist jedes Element (außer dem ersten Element) das Quadrat der vorherigen Zahl.

Gib die Länge des längsten Quadratstreifens in Zahlen zurück, oder gib -1 zurück, wenn kein Quadratstreifen vorhanden ist.

Eine Teilsequenz ist ein Array, das von einem anderen Array abgeleitet werden kann, indem einige oder keine Elemente gelöscht werden, ohne die Reihenfolge der verbleibenden Elemente zu ändern.

Beispiel 1:

• Eingabe: nums = [4,3,6,16,8,2]
• Ausgabe: 3
• Erklärung: Wählen Sie die Teilsequenz [4,16,2]. Nach dem Sortieren wird es zu [2,4,16].
  • 4 = 2 * 2.
  • 16 = 4 * 4.
  • Daher ist [4,16,2] ein quadratischer Streifen.
  • Es kann gezeigt werden, dass jede Teilfolge der Länge 4 kein quadratischer Streifen ist.

Beispiel 2:

• Eingabe: nums = [2,3,5,6,7]
• Ausgabe: -1
• Erklärung: Es gibt keinen quadratischen Streifen in Zahlen, also geben Sie -1 zurück.

Einschränkungen:

• 2 <= nums.length <= 10⁵
• 2 <= nums[i] <= 10⁵

Hinweis:

1. Mit den Einschränkungen beträgt die Länge des längsten möglichen Quadratstreifens 5.
2. Speichern Sie die Elemente von Nums in einem Satz, um schnell zu überprüfen, ob sie vorhanden sind.

Lösung:

Wir müssen den längsten quadratischen Streifen im Nums-Array identifizieren. Ein Square Streak ist eine Teilfolge, bei der jedes nachfolgende Element das Quadrat des vorherigen Elements ist und mindestens zwei Elemente lang sein muss.

Hier ist der Lösungsansatz:

1. Verwenden Sie ein Set für die schnelle Suche:

   • Speichern Sie die Zahlen in einem Satz, um schnell zu überprüfen, ob das Quadrat eines Elements auch im Array enthalten ist.

2. Durch das Array iterieren:

   • Versuchen Sie, für jede Zahl im Array ausgehend von dieser Zahl einen quadratischen Streifen zu bilden.
   • Überprüfen Sie, ob das Quadrat der aktuellen Zahl im Satz vorhanden ist, und verlängern Sie den Streak so lange, bis es keine weitere Quadratübereinstimmung mehr gibt.

3. Maximale Länge des Tracks:

   • Verfolgen Sie die maximale Länge aller möglichen quadratischen Streifen. Wenn kein quadratischer Streifen gefunden wird, geben Sie -1 zurück.

4. Optimierung:

   • Sortieren Sie das Array, bevor Sie jedes Element überprüfen, um sicherzustellen, dass die Teilsequenz in aufsteigender Reihenfolge überprüft wird. Dies hilft, überflüssige Kontrollen zu vermeiden.

Lassen Sie uns diese Lösung in PHP implementieren: 2501. Längster quadratischer Streifen in einem Array

  
  
  Erläuterung:




Sortieren: Das Sortieren von Zahlen stellt sicher, dass wir Sequenzen in aufsteigender Reihenfolge überprüfen können.

Set Lookup: Durch die Verwendung von array_flip wird eine satzartige Struktur für $numSet mit $nums als Schlüssel erstellt, was schnelle Existenzprüfungen ermöglicht.

Durchlaufen Sie jede Zahl: Überprüfen Sie für jede Zahl in Zahlen, ob das Quadrat der aktuellen Zahl in der Menge enthalten ist. Wenn ja, setzen Sie den Streak fort. Andernfalls unterbrechen Sie den Streak und prüfen Sie, ob er der längste gefundene ist.



  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n log n) aufgrund der Sortierung, wobei n die Anzahl der Elemente ist in Zahlen. Die nachfolgenden Suchvorgänge und Quadratstreifenprüfungen sind O(n).

Raumkomplexität: O(n), hauptsächlich zum Speichern von Zahlen im Set.


Diese Lösung findet effizient den längsten quadratischen Streak oder gibt -1 zurück, wenn kein gültiger Streak vorhanden ist.

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 vonLängster quadratischer Streifen in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!