Gegebene n Paare von Zahlen, wählen Sie k Paare, so dass die Differenz zwischen dem minimalen Wert und dem maximalen Wert minimal ist. Beachten Sie, dass 2 Zahlen in 1 Paar nicht getrennt werden können. Beispiel (n = 5, k = 3) :
%Vor%In diesem Fall ergibt die Wahl von (5,4) (1,5) (1,0) eine Differenz von 5 (max ist 5, min ist 0) . Ich suche nach einem effizienten Weg (n log n) , dies zu tun, da die Eingabe ziemlich groß sein wird und ich nicht jeden möglichen Fall durchgehen möchte.
Danke.
HINWEIS: Kein Code erforderlich. Eine Erklärung der Lösung ist genug.
Hier ist eine Methode mit O(n log n) zeitlicher Komplexität:
Sortiere das Array zuerst nach der kleineren Zahl im Paar. Iteriere nun vom letzten Element im sortierten Array (dem Paar mit dem höchsten Minimum) zurück.
Wenn wir rückwärts gehen, haben die bereits besuchten Elemente notwendigerweise ein gleiches oder höheres Minimum als das aktuelle Element. Speichern Sie die besuchten Paare in einem Max-Heapspeicher entsprechend der maximalen Nummer im besuchten Paar. Wenn die Größe des Heapspeichers kleiner als k-1 ist, fügen Sie den Heap hinzu.
Sobald die Größe des Heapspeichers gleich k-1 ist, beginnen Sie mit der Aufzeichnung und vergleichen Sie das bisher beste Intervall. Wenn die Größe des Heapspeichers k-1 überschreitet, setzen Sie das maximale Element ab. Der Heap enthält garantiert die ersten k-1 -Paare, bei denen die minimale Zahl größer oder gleich der aktuellen minimalen Zahl ist und die maximale ist am kleinsten (da wir das maximale Element abbrechen, wenn die Größe des Heapspeichers k-1 überschreitet).
Gesamtzeit O(n log n) zum Sortieren + O(n log n) zum Iterieren und Verwalten des Heap = O(n log n) insgesamt.
Beispiel:
%Vor%Lasst uns sortierte Arrays behalten: eines, das nach minimaler Anzahl im Paar sortiert ist und anderes bis maximal. Lässt sich über das erste Array iterieren und die minimale Anzahl in der Antwort fixieren. Wir können den Zeiger auf die k-te Nummer im zweiten Array halten. Wenn wir zum nächsten Paar gehen, entfernen wir alle Paare mit weniger Minimalwert aus dem zweiten Array und leiten den Zeiger bei Bedarf weiter. Um die Position in log n Zeit im zweiten Array zu finden, können wir zusätzliche Karten zwischen Paaren und Positionen speichern.
Tags und Links algorithm combinations difference