. Finden Sie den K-ten kleinsten Paarabstand

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.

Gegeben ein ganzzahliges Array nums und eine ganze Zahl k, gib den k kleinsten Abstand zwischen allen Paaren nums[i] und nums[j] zurück, wobei 0 < ;= i < j < nums.length.

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 1stkleinste 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 <= n <= 104

0 <= nums[i] <= 106

1 <= k <= n * (n - 1) / 2


Hinweis:


Binäre Suche nach der Antwort. Wie können Sie überprüfen, wie viele Paare einen Abstand von <= X haben?


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:



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.
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).
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 effizient mit einem Zwei-Punkte-Ansatz erfolgen.
Binären Suchbereich anpassen: Passen Sie den binären Suchbereich an, abhängig von der Anzahl der Paare mit einem Abstand kleiner oder gleich der Mitte. 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



          

            
  

            
        
Das obige ist der detaillierte Inhalt von. Finden Sie den K-ten kleinsten Paarabstand. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!