719. Finden Sie den K-ten kleinsten Paarabstand

Schwierigkeit: Schwer

Themen: Array, Zwei Zeiger, Binäre Suche, Sortieren

Der Abstand eines Paares der ganzen Zahlen a und b ist definiert als die absolute Differenz zwischen a und b.

Angesichts eines ganzzahligen Arrays nums und einer ganzen Zahl k, gebe den k^ten kleinsten Abstand zwischen allen Paaren nums[i] und nums[j] zurück, wobei 0 .

Beispiel 1:

• Eingabe: nums = [1,3,1], k = 1
• Ausgabe: 0
• Erklärung: Hier sind alle Paare:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

Dann ist das 1^st kleinste Distanzpaar (1,1) und sein Abstand ist 0.

Beispiel 2:

• Eingabe: nums = [1,1,1], k = 2
• Ausgabe: 0

Beispiel 3:

• Eingabe: nums = [1,6,1], k = 3
• Ausgabe: 5

Einschränkungen:

• n == nums.length
• 2 4
• 0 6
• 1

Hinweis:

1. Binäre Suche nach der Antwort. Wie können Sie überprüfen, wie viele Paare einen Abstand

Lösung:

Wir können eine Kombination aus binärer Suche und Zwei-Zeiger-Technik verwenden. Hier ist ein schrittweiser Ansatz zur Lösung dieses Problems:

Ansatz:

1. Array sortieren: Sortieren Sie zunächst die Array-Nummern. Das Sortieren hilft bei der effizienten Berechnung der Anzahl von Paaren mit einem Abstand, der kleiner oder gleich einem bestimmten Wert ist.

2. Binäre Suche nach Entfernung: Verwenden Sie die binäre Suche, um die k-kleinste Entfernung zu finden. Der Suchraum für die Abstände reicht von 0 (kleinstmöglicher Abstand) bis max(nums) - min(nums) (größter möglicher Abstand).

3. Paare mit Abstand ≤ Mitte zählen: Zählen Sie für jeden Mittelwert in der binären Suche die Anzahl der Paare mit einem Abstand kleiner oder gleich Mitte. Dies kann mithilfe eines Zwei-Punkte-Ansatzes effizient erfolgen.

4. Binären Suchbereich anpassen: Abhängig von der Anzahl der Paare mit einem Abstand kleiner oder gleich der Mitte, passen Sie den binären Suchbereich an. Wenn die Anzahl kleiner als k ist, erhöhen Sie die Untergrenze. Andernfalls verringern Sie die Obergrenze.

Lassen Sie uns diese Lösung in PHP implementieren: 719. Finden Sie den K-ten kleinsten Paarabstand

Erläuterung:

• countPairsWithDistanceLessThanOrEqualTo: Diese Funktion zählt, wie viele Paare einen Abstand haben, der kleiner oder gleich der Mitte ist. Es verwendet zwei Zeiger, wobei rechts das aktuelle Element ist und links angepasst wird, bis die Differenz zwischen Zahlen[rechts] und Zahlen[links] kleiner oder gleich der Mitte ist.

• smallestDistancePair: Diese Funktion verwendet eine binäre Suche, um den k-kleinsten Abstand zu finden. Die unteren und oberen Werte definieren den aktuellen Suchbereich für die Entfernungen. Der Mittelwert wird mit der Funktion countPairsWithDistanceLessThanOrEqualTo überprüft. Abhängig vom Ergebnis wird der Suchraum angepasst.

Dieser Algorithmus findet effizient den k-ten kleinsten Paarabstand mit einer Zeitkomplexität von O(n log(max(nums) - min(nums)) n log n).

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