. Maximaler Abstand in Arrays

王林
Freigeben: 2024-08-17 06:35:09
Original
826 Leute haben es durchsucht

. Maximum Distance in Arrays

624. Maximaler Abstand in Arrays

Schwierigkeit:Mittel

Themen:Array, Greedy

Sie erhalten m Arrays, wobei jedes Array in aufsteigender Reihenfolge sortiert ist.

Sie können zwei Ganzzahlen aus zwei verschiedenen Arrays (jedes Array wählt eine aus) auswählen und den Abstand berechnen. Wir definieren den Abstand zwischen zwei ganzen Zahlen a und b als ihre absolute Differenz |a - b|.

Gib die maximale Entfernung zurück.

Beispiel 1:

  • Eingabe: arrays = [[1,2,3],[4,5],[1,2,3]]
  • Ausgabe: 4
  • Erklärung: Eine Möglichkeit, den maximalen Abstand 4 zu erreichen, besteht darin, 1 im ersten oder dritten Array auszuwählen und 5 im zweiten Array auszuwählen.

Beispiel 2:

  • Eingabe: arrays = [[1],[1]]
  • Ausgabe: 0

Einschränkungen:

  • m == arrays.length
  • 2 <= m <= 105
  • 1 <= arrays[i].length <= 500
  • -104 <= arrays[i][j] <= 104
  • arrays[i] wird in aufsteigender Reihenfolge sortiert.
  • Es werden höchstens 105Ganzzahlen in allen Arrays vorhanden sein.

Lösung:

Wir müssen den maximal möglichen Abstand zwischen zwei ganzen Zahlen berechnen, die jeweils aus unterschiedlichen Arrays ausgewählt werden. Die wichtigste Beobachtung ist, dass der maximale Abstand höchstwahrscheinlich zwischen dem Minimalwert eines Arrays und dem Maximalwert eines anderen Arrays liegt.

Um dieses Problem zu lösen, können wir die folgenden Schritte ausführen:

  1. Verfolgen Sie den Mindest- und Höchstwert, während Sie die Arrays durchlaufen.
  2. Berechnen Sie für jedes Array den potenziellen maximalen Abstand, indem Sie das Minimum des aktuellen Arrays mit dem globalen Maximum und das Maximum des aktuellen Arrays mit dem globalen Minimum vergleichen.
  3. Aktualisieren Sie das globale Minimum und Maximum, während Sie fortfahren.

Lassen Sie uns diese Lösung in PHP implementieren: 624. Maximaler Abstand in Arrays






Erläuterung:

  • min_value und max_value werden mit den Minimal- und Maximalwerten des ersten Arrays initialisiert.
  • Während wir jedes Array beginnend mit dem zweiten durchlaufen:
    • Wir berechnen den Abstand, indem wir das globale Minimum mit dem Maximum des aktuellen Arrays und das globale Maximum mit dem Minimum des aktuellen Arrays vergleichen.
    • Aktualisieren Sie die max_distance, wenn eine größere Entfernung gefunden wird.
    • Aktualisieren Sie min_value und max_value, um die bisher gefundenen Mindest- und Höchstwerte widerzuspiegeln.
  • Abschließend gibt die Funktion die maximal gefundene Entfernung zurück.

Diese Lösung läuft in O(m)-Zeit, wobei m die Anzahl der Arrays ist, was sie angesichts der Problembeschränkungen effizient macht.

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. Maximaler Abstand in Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!