Gibt es eine Möglichkeit, in O(n) time die Kombination der Elemente in k sorted arrays zu erhalten, was mir den geringsten Unterschied zwischen den minimalen und maximalen Elementen in der Kombination gibt? n ist die Gesamtzahl der Elemente in diesen Arrays.
Hier ist ein Beispiel:
%Vor%Und für diese Arrays sind unten alle möglichen Kombinationen:
%Vor% In diesem Fall sind die Unterschiede der minimalen und maximalen Elemente 6, 5, 13, 11 für die obigen Kombinationen. Also, was ich zurückgeben sollte, ist comb2 , da der Unterschied für diese Kombination der kleinste ist.
Falls es hilft, gibt es keine wiederholenden Elemente in der gesamten Menge von Werten in den ursprünglichen Arrays.
Ordnen Sie die Zahlen zusammen und jedes Array separat:
%Vor% Für jede Wahl, die wir nicht machen, um eine äußere Zahl (die rechte oder die äußerste) zu entfernen, ist die nächste Folge von Auswahlmöglichkeiten klar. Wenn wir c2 (18) fixieren, können wir von links nach oben bis b2 gehen. Aber wenn wir c2 entfernen, ist die einzige Änderung in der linken Grenze innerhalb des c -Arrays selbst.
Beginne mit den meisten, die wir von links für das fixierte Element ganz rechts entfernen können. Das Entfernen eines Elements aus dem rechten wird immer nur die linke Grenze verschieben, wenn das Element eines der letzten beiden in einem Array ist. Entfernen Sie immer das rechte Element und aktualisieren Sie bei Bedarf die linke Grenze. Wähle das beste gesehene Intervall. (Beachten Sie, dass die Elemente zwischen den äußeren beiden Elementen keine Rolle spielen, wir können aus jedem Array einen Vertreter als Vertreter auswählen.)
Die Komplexität der gleitenden Fensteriteration nach dem Sortieren ist O(n) , da bei sortierten Arrays die kumulativen linksgebundenen Aktualisierungen O(n) sind.
TL; DR Ich denke nicht, dass dies in O(n) möglich ist (obwohl ich es nicht beweisen kann), also können Sie unten zwei O(n*logk) Lösungen finden.
Lösung 1:
Verwenden Sie min-haufen der Größe k wie beschrieben hier .
Lösung 2 (meine)
Wir brauchen 3 zusätzliche Arrays, nennen wir sie A , B und C . Lassen Sie uns auch die Eingabe-Arrays "Original-Arrays" nennen.
A hat die Größe n und behält alle Elemente aller ursprünglichen Arrays in sortierter Reihenfolge B hat auch die Größe n und behält Informationen über die Quelle der Elemente im Array A , d. h. von dem das ursprüngliche Array-Element in A von C hat die Größe k und es enthält während des Prozesses zuletzt gesehene Indizes von Elementen aus den ursprünglichen Arrays (siehe unten) Da die ursprünglichen Arrays sortiert sind, können Sie die Arrays A und B in O(n*logk) time erstellen, indem Sie verwenden k-way merge algorithm (ein Beispiel ist mit min-heap: Zu Beginn werden die ersten Elemente aller ursprünglichen Arrays in min heap abgelegt; dann wird das kleinste Element aus dem Min-Heap iterativ eingefügt, in B , und push das nächste Element aus dem gleichen ursprünglichen Array in Heap). Für das von Ihnen bereitgestellte Beispiel sehen die Arrays A und B folgendermaßen aus: A = [5, 6, 7, 11, 18], B = [1, 2, 1, 0, 2] ( 5 stammt vom zweiten Original-Array, 6 stammt vom dritten Original-Array usw.).
Jetzt verwenden wir Schiebefenstertechnik , um das Fenster der Größe mindestens k zu finden, dessen Unterschied zwischen Letztes und erstes Element ist das kleinste. Die Idee besteht darin, durch das Array B zu iterieren, bis wir Elemente aus allen ursprünglichen Arrays "sammeln" - das bedeutet, dass wir eine Kombination gefunden haben und nun einfach den Unterschied zwischen dem ersten und letzten Element überprüfen Kombination. Array C kommt nun in das Spiel - wir initialisieren alle seine Elemente mit -1 und setzen C[i] auf den letzten Index eines Elements aus dem ursprünglichen Array i . Sobald wir das erste gleitende Fenster gefunden haben, das Elemente von allen ursprünglichen Arrays enthält, erweitern wir dieses Fenster weiter nach rechts und verkleinern es von links, während wir die Eigenschaft beibehalten, dass Repräsentanten aller ursprünglichen Arrays innerhalb des Fensters sind. Also wird der Algorithmus so aussehen:
Lassen Sie uns das anhand Ihres Beispiels erklären:
%Vor% Die Zeitkomplexität ist O(n*logk) , weil das Erstellen von Arrays A und B von k sortierten Arrays O(n*logk) benötigt und während der Schleife jeweils n elements höchstens zweimal geprüft wird, also ist dieser Teil O(n) und schließlich O(n*logk + n) = O(n*logk) . Wenn Sie Original-Arrays zu einem zusammenführen, ist dies das Beste, was Sie bekommen können :
Man kann zeigen, dass kein auf Vergleichen basierender k-way Merge-Algorithmus existiert mit einer Laufzeit in O (n f (k)), wobei f asymptotisch langsamer wächst als ein Logarithmus.
Hoffe, das hilft!
Tags und Links algorithm arrays time-complexity big-o