Bei einem sortierten Array von einzelnen ganzen Zahlen die Mindestanzahl von Schritten, die erforderlich sind, um die Ganzzahlen zusammenhängend zu machen? Hier ist die Bedingung: In einem Schritt kann nur ein Element geändert und um 1 erhöht oder verringert werden. Zum Beispiel, wenn wir 2,4,5,6 haben, dann kann '2' zu '3' gemacht werden, wodurch die Elemente zusammenhängend werden ( 3,4,5,6 ). Daher sind die minimalen Schritte hier 1. Ähnlich für das Array: 2,4,5,8 :
Somit ist die Sequenz jetzt 3,4,5,6 und die Anzahl der Schritte ist 3.
Ich habe es wie folgt versucht, bin mir aber nicht sicher, ob es korrekt ist?
%Vor%Danke.
Die intuitive Vermutung ist, dass das "Zentrum" der optimalen Sequenz das arithmetische Mittel ist, aber das ist nicht der Fall. Lassen Sie uns die richtige Lösung mit etwas Vektormathematik finden:
Teil 1: Unter der Annahme, dass die erste Zahl in Ruhe gelassen wird (wir gehen später auf diese Annahme ein), berechnen Sie die Unterschiede, so dass 1 12 3 14 5 16 - 1 2 3 4 5 6 0 -10 0 -10 0 -10 ergeben würde.
Nebenbemerkung: Beachten Sie, dass ein "zusammenhängendes" Array nach Ihrer implizierten Definition eine ansteigende arithmetische Sequenz mit der Differenz 1 wäre. (Beachten Sie, dass es andere vernünftige Interpretationen Ihrer Frage gibt. co_de% muss zusammenhängend sein, oder 5 4 3 2 1 muss zusammenhängend sein, oder 5 3 1 muss zusammenhängend sein. Sie haben auch nicht angegeben, ob negative Zahlen anders behandelt werden sollen.)
Theorem: Die zusammenhängenden Zahlen müssen zwischen der minimalen und maximalen Zahl liegen. [Beweis dem Leser überlassen]
Teil 2: Nun kehren wir zu unserem Beispiel zurück, vorausgesetzt, wir haben die 30 Schritte (sum (abs ( 1 2 3 2 3 )) = 30) benötigt, um 0 -10 0 -10 0 -10 in 1 12 3 14 5 16 zu verwandeln. Das ist eine richtige Antwort. Aber 1 2 3 4 5 6 + c ist auch eine Antwort, die eine arithmetische Folge der Differenz 1 für jede Konstante c ergibt. Um die Anzahl der "Schritte" zu minimieren, müssen wir ein geeignetes c auswählen. In diesem Fall erhöhen wir jedes Mal, wenn wir c erhöhen oder verringern, die Anzahl der Schritte um N = 6 (die Länge des Vektors). Wenn wir zum Beispiel unsere ursprüngliche Sequenz 0 -10 0 -10 0 -10 in 1 12 3 14 5 16 (c = 2) umwandeln wollten, wären die Unterschiede 3 4 5 6 7 8 und 2 -8 2 -8 2 -8 gewesen.
Das ist jetzt sehr klar, wenn Sie es sich visuell vorstellen können, aber es ist schwierig, es in Text einzugeben. Zuerst haben wir unseren Differenzvektor genommen. Stellen Sie sich vor, Sie hätten es so gezeichnet:
%Vor% Es steht uns frei, diesen Vektor nach oben und unten zu verschieben, indem wir 1 von allem addieren oder subtrahieren. (Dies entspricht dem Finden von c.) Wir möchten die Verschiebung finden, die die Anzahl von sum(abs(2 -8 2 -8 2 -8))=30 minimiert, die Sie sehen (der Bereich zwischen der Kurve und der x-Achse). Dies ist NICHT der Durchschnitt (das wäre Minimierung der Standardabweichung oder des RMS-Fehlers , nicht der absolute Fehler). Um das minimierende c zu finden, stellen wir uns das als Funktion vor und betrachten es als Ableitung. Wenn die Unterschiede alle weit von der x-Achse entfernt sind (wir versuchen, | zu machen), ist es sinnvoll, diese zusätzlichen Daten einfach nicht hinzuzufügen, also verschieben wir die Funktion in Richtung der x-Achse. Jedes Mal, wenn wir c verringern, verbessern wir die Lösung um 6. Nehmen wir nun an, dass eines der 101 112 103 114 105 116 s die x-Achse passiert. Jedes Mal, wenn wir c verringern, verbessern wir die Lösung um 5-1 = 4 (wir sparen 5 Arbeitsschritte, müssen aber einen zusätzlichen Arbeitsschritt für * unterhalb der x-Achse ausführen). Wenn HALF * s hinter der x-Achse liegen, können wir die Lösung NICHT MEHR VERBESSERN (Ableitung: 3-3 = 0). (In der Tat fangen wir bald an, die Lösung schlechter zu machen und können sie nie wieder verbessern. Wir haben nicht nur das Minimum dieser Funktion gefunden, sondern wir können sehen, dass es ein globales Minimum ist.)
Daher lautet die Lösung wie folgt: Stellen Sie sich vor, die erste Nummer ist vorhanden. Berechnen Sie den Vektor der Unterschiede. Minimiere die Summe des absoluten Wertes dieses Vektors; Tun Sie dies, indem Sie den Median der Differenzen finden und subtrahieren Sie diesen von den Differenzen, um einen verbesserten Differenzenvektor zu erhalten. Die Summe des absoluten Wertes des "verbesserten" Vektors ist Ihre Antwort. Das ist * Die Lösungen gleicher Optimalität werden (wie oben beschrieben) immer "benachbart" sein. Eine eindeutige Lösung existiert nur, wenn eine ungerade Anzahl von Zahlen vorhanden ist; andernfalls, wenn es eine gerade Anzahl von Zahlen gibt, UND der Differenzenmedian keine Ganzzahl ist, haben die gleichoptimalen Lösungen Differenzvektoren mit Korrekturfaktoren irgendeiner Zahl zwischen den beiden Medianen.
Also ich denke, das wäre ohne ein abschließendes Beispiel nicht vollständig.
O(N)
2 3 4 10 14 14 15 100 - 2 3 4 5 6 7 8 9 = 2 3 4 10 14 14 15 100
0 0 0 -5 -8 -7 -7 -91 Medianfundingalgorithmus durchführen, um sie zu extrahieren ... O(N) und -5
-7 + 5 = 2 3 4 5 6 7 8 9 und die neuen Unterschiede sind 7 8 9 10 11 12 13 14 * 5 5 5 0 -3 -2 -2 -86 = 108 Schritte * (wir erhalten dies, indem wir Schritt 2 mit unserem neuen Ziel wiederholen, oder indem wir jeder Zahl der vorherigen Differenz 5 hinzufügen ... aber da Sie sich nur um die Summe kümmern, würden wir einfach 8 * 5 (Vektor Länge mal korrekter Faktor) zur zuvor berechneten Summe)
Alternativ hätten wir auch -6 oder -7 als Korrekturfaktor verwenden können. Nehmen wir an, wir haben -7 ...
5+5+5+0+3+2+2+86 + 7 = 2 3 4 5 6 7 8 9 und die neuen Unterschiede wären 9 10 11 12 13 14 15 16
Wenn Sie dies selbst simulieren, können Sie sehen, dass die Anzahl der Schritte zu & gt; 108 wird, wenn Offsets weiter entfernt von dem Bereich [-5, -7] genommen werden.
Pseudocode:
%Vor%Python:
%Vor%bearbeiten:
Es stellt sich heraus, dass für Arrays mit verschiedenen ganzen Zahlen dies einer einfacheren Lösung : wählt eines der (bis zu 2) Mediane aus, vorausgesetzt, es bewegt sich nicht und verschiebt andere Zahlen entsprechend . Diese einfachere Methode gibt oft falsche Antworten, wenn Duplikate haben, aber das OP hat das nicht gefragt, also wäre das eine einfachere und elegantere Lösung. Zusätzlich können wir den Beweis, den ich in dieser Lösung gegeben habe, verwenden, um die Lösung "gehe davon aus, dass sich der Median nicht bewegt" wie folgt zu rechtfertigen: Der Korrekturfaktor wird immer in der Mitte des Arrays liegen (dh der Median der Differenzen wird sein) vom Median der Zahlen). So kann jede Einschränkung, die auch dies garantiert, verwendet werden, um Variationen dieses Denkfehlers zu erzeugen.
Erhalte eines der Mediane aller Zahlen. Da die Zahlen bereits sortiert sind, sollte dies keine große Sache sein. Angenommen, der Median bewegt sich nicht. Berechnen Sie dann die Gesamtkosten für das Verschieben aller Nummern entsprechend. Dies sollte die Antwort geben.
Community-Bearbeitung:
%Vor%Dies ist wahrscheinlich keine ideale Lösung, sondern eine erste Idee.
Gegeben sei eine sortierte Sequenz [x1], x2, ..., xn:
Schreiben Sie eine Funktion, die die Unterschiede eines Elements zum vorherigen und zum nächsten Element zurückgibt, dh ( x n ) - x
Wenn der Unterschied zum vorherigen Element & gt; 1, müssten Sie alle vorherigen Elemente um x n - x n erhöhen -1 - 1. Das heißt, die Anzahl der notwendigen Schritte würde um die Anzahl der vorherigen Elemente × ( x n ) zunehmen - x n -1 - 1). Nennen wir diese Nummer a .
Wenn der Unterschied zum nächsten Element & gt; 1 ist, müssten Sie alle folgenden Elemente um x n +1 - x n - 1. Das heißt, die Anzahl der notwendigen Schritte würde um die Anzahl der nachfolgenden Elemente × ( x n +1 - x n - 1). Nennen wir diese Nummer b .
Wenn a & lt; b , dann erhöhen Sie alle vorherigen Elemente, bis sie an das aktuelle Element angrenzen. Wenn a & gt; b , dann verringern Sie alle nachfolgenden Elemente, bis sie an das aktuelle Element angrenzen. Wenn a = b ist, spielt es keine Rolle, welche dieser beiden Aktionen gewählt wird.
Fügen Sie die Anzahl der im vorherigen Schritt durchgeführten Schritte hinzu (indem Sie die Gesamtzahl der erforderlichen Schritte entweder um a oder b erhöhen) und wiederholen Sie bis Alle Elemente sind zusammenhängend.
Stellen Sie sich zunächst vor, dass wir ein beliebiges Ziel aus zusammenhängenden steigenden Werten auswählen und dann die Kosten (Anzahl der erforderlichen Schritte) berechnen, um das Array zu ändern, dem das Array entspricht.
%Vor%Da das Eingabearray bereits geordnet und eindeutig ist, nimmt es streng zu. Aus diesem Grund kann gezeigt werden, dass die Unterschiede immer nicht ansteigen.
Wenn wir das Ziel ändern, indem wir es um 1 erhöhen, ändern sich die Kosten. Jede Position, in der die Differenz aktuell positiv oder Null ist, wird um 1 erhöht. Jedes positive Ergebnis, bei dem die Differenz derzeit negativ ist, führt zu einer Kostensenkung um 1:
%Vor%Wenn wir das Ziel dagegen um 1 verringern, führt jede Position, in der die Differenz aktuell positiv ist, zu einer Kostensenkung um 1, während jede Position, bei der die Differenz null oder negativ ist, um 1 erhöht wird :
%Vor%Um die optimalen Werte für das Zielarray zu finden, müssen wir ein Ziel finden, so dass jede Änderung (Inkrement oder Dekrement) die Kosten nicht verringert. Beachten Sie, dass ein Inkrement des Ziels die Kosten nur verringern kann, wenn mehr Positionen mit einer negativen Differenz vorhanden sind als mit einer Null oder einer positiven Differenz. Ein Dekrement kann die Kosten nur verringern, wenn es mehr Positionen mit einer positiven Differenz als mit einer Null oder negativen Differenz gibt.
Hier sind einige Beispielverteilungen von Differenzzeichen. Denken Sie daran, dass das Differenzen-Array nicht ansteigt, also müssen Positive immer zuerst und Negative zuletzt sein:
%Vor% Beachten Sie, dass wenn eines der zentralen Elemente (mit C markiert) null ist, das Ziel optimal sein muss. In einem solchen Fall wird bestenfalls jedes Inkrement oder Dekrement die Kosten nicht ändern, aber es kann es erhöhen. Dieses Ergebnis ist wichtig, weil es uns eine triviale Lösung gibt. Wir wählen ein Ziel so, dass a[n/2] unverändert bleibt. Es kann andere mögliche Ziele geben, die die gleichen Kosten ergeben, aber es gibt definitiv keine, die besser sind. Hier ist der ursprüngliche Code, der geändert wurde, um diese Kosten zu berechnen:
Sie können es nicht tun, indem Sie einmal auf dem Array iterieren, das ist sicher.
Sie müssen zuerst den Unterschied zwischen jeweils zwei Zahlen überprüfen, zum Beispiel:
2,7,8,9 kann 2,3,4,5 mit 18 Schritten oder 6,7,8,9 mit 4 Schritten sein.
Erstellen Sie ein neues Array mit dem Unterschied: Für 2,7,8,9 ist es 4,1,1 . Jetzt können Sie entscheiden, ob Sie die erste Zahl erhöhen oder verringern möchten.
Nehmen wir an, dass das zusammenhängende Array etwa so aussieht -
c c + 1 c + 2 c + 3 .. und so weiter
Nun nehmen wir ein Beispiel -
5 7 8 10
Das zusammenhängende Array ist in diesem Fall -
cc + 1c + 2c + 3
Um die minimalen Schritte zu erhalten, sollte die Summe des Betrags der Differenz der ganzen Zahlen (vorher und nachher) des i-ten Index das Minimum sein. In diesem Fall
(c-5) ^ 2 + (c-6) ^ 2 + (c-6) ^ 2 + (c-7) ^ 2 sollte minimal sein
Sei f (c) = (c-5) ^ 2 + (c-6) ^ 2 + (c-6) ^ 2 + (c-7) ^ 2 = 4c ^ 2 - 48c + 146
Differentialrechnung anwenden, um die Minima zu erhalten,
f '(c) = 8c - 48 = 0 = & gt; c = 6
Also unser zusammenhängendes Array ist 6 7 8 9 und die minimalen Kosten hier sind 2.
Um es zusammenzufassen, erzeuge einfach f (c), erhalte das erste Differential und finde c heraus. Dies sollte O (n) nehmen.
O(N*M)
Wenn man durch jeden Punkt im Array a eine Linie zeichnet, dann ist y0 ein Wert, bei dem jede Zeile am Index 0 beginnt. Dann ist die Antwort das Minimum aus der Anzahl der Schritte, die benötigt werden, um von a zu jeder Zeile zu kommen, die bei y0 beginnt, in Python:
Tags und Links algorithm