Man betrachte zwei sortierte Arrays von ganzen Zahlen und der Größe bzw. mit . Zum Beispiel ist , .Y m n m < n X = ( 1 , 4 ) Y = ( 2 , 10 , 11 )
Wir sagen, dass eine Übereinstimmung eine Art ist, jedes Element von mit einem Element von so zu paaren , dass keine zwei Elemente von mit demselben Element von gepaart werden . Die Kosten eines Matchings sind nur die Summe der absoluten Werte der Differenzen in den Paaren.Y X Y
Zum Beispiel können wir mit , die Paare die dann gekostet haben . Wenn wir die Paare hätten die Kosten . Wenn wir die Paare hätten, wären die Kosten .Y = ( 2 , 10 , 11 ) ( 7 , 2 ) , ( 11 , 10 ) 5 + 1 = 6 ( 7 , 10 ) , ( 11 , 11 ) 3 + 0 = 3 ( 7 , 11 ) , ( 11 , 10 ) +
Als weiteres Beispiel nimm , . Wir können die Paare zu einem Preis von . Die Paare (7,10), (11,11), (14,18) kosten 7 .
Die Aufgabe besteht darin, Code zu schreiben, der bei zwei sortierten Arrays von Ganzzahlen und eine minimale Kostenanpassung berechnet.
Testfälle
[1, 4], [2, 10, 11] => [[1, 2], [4, 10]]
[7, 11], [2, 10, 11] => [[7, 10], [11, 11]]
[7, 11, 14], [2, 10, 11, 18] => [[7, 10], [11, 11], [14, 18]]
Antworten:
Brachylog , 16 Bytes
Probieren Sie es online!
Erläuterung
Da wir uns
I
zu Beginn zu einer ganzen Zahl vereinigen, probieren wir Dinge von kleinen WertenI
bis zu großen Werten von ausI
, was bedeutet, dass das erste Mal, wenn es erfolgreich sein wird, notwendigerweise die Paarung mit kleinsten absoluten Differenzen sein wird.quelle
Jelly ,
15 14 1211 BytesProbieren Sie es online!
Rohe Gewalt. Nimmt als Eingabe dann X .Y. X
quelle
L}
anstelle von arbeiten⁹L¤
?ÐṂḢ
->ÞḢ
um ein Byte zu speichern.Haskell,
787776 BytesTIO hat keine
Data.Lists
, also keine Verbindung.Grundsätzlich der gleiche Algorithmus wie in @ dylnans Antwort .
Edit: -1 Byte dank @BMO.
quelle
JavaScript (ES7), 121 Byte
Übernimmt die 2 Arrays in Currying-Syntax
(x)(y)
.Probieren Sie es online!
quelle
J , 24 Bytes
Probieren Sie es online!
Erklärung / Demonstration:
Ein dyadisches Verb,
x f y
-/
findet die Unterschiede(0{]#~1>])"1
Behalten Sie für jede Zeile nur die nicht positiven Werte bei und nehmen Sie den ersten:[:,@:
verflacht die Liste (um der Form des linken Arguments zu entsprechen)[-
subtrahieren Sie die min. Unterschiede zum linken Argument[,.
Heften Sie sie an das linke Argument:quelle
Pyth , 18 Bytes
Probieren Sie es hier aus!
quelle
Oktave , 66 Bytes
Anonymous Funktion , die Zeilenvektoren nimmt
X
,Y
als Eingänge und gibt eine 2-Zeilenmatrix , wobei jede Spalte ein Paar der passenden.Probieren Sie es online!
quelle
Pyth , 16 Bytes
Versuchen Sie es online hier , oder prüfen Sie alle Testfälle auf einmal hier .
quelle
MATL , 16 Bytes
Eingänge sind
X
dannY
.Die Übereinstimmung wird mit den ersten Werten jedes Paares (dh
X
) in der ersten Zeile und den zweiten Werten jedes Paares in der zweiten Zeile ausgegeben .Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
quelle
Jelly , (10?) 12 Bytes
10 Bytes, wenn nur die Elemente von Y benötigt werden (siehe Kommentare) - nicht sicher, ob dies in der Spezifikation zulässig ist (und dies sollte möglicherweise nicht der Fall sein, da andere Antworten dieses Detail bereits implementieren).
Dies kann durch Entfernen des Schleppers erreicht werden
⁸ż
.Eine dyadische Verknüpfung, die X links und Y rechts akzeptiert.
(
œc⁹L¤ạS¥ÞḢż@
und die 10 Bytesœc⁹L¤ạS¥ÞḢ
machen dasselbe mit Y auf der linken und X auf der rechten Seite).Probieren Sie es online!
Wie?
quelle
JavaScript (ES7), 100 Byte
Neu hier; Alle Tipps / Korrekturen wäre dankbar! Bei einem früheren Versuch wurden Probleme beim Sortieren eines Arrays übersehen, das einen
NaN
Wert enthält. Hoffentlich habe ich diesmal nichts verpasst.Erwartet zwei Argumente wie X , Y , respectively. Probieren Sie es online!
Scheint der Lösung von @ Arnauld ähnlich zu sein
Erläuterung
Beruht auf der Tatsache, dass gegebene X , Y sortiert sind, gibt es eine Lösung von Minimalkostenübereinstimmungen, bei denen, wenn alle Paare angeordnet sind, um die Reihenfolge der Elemente von X beizubehalten , alle Y- Elemente in der Anordnung auch ihre Reihenfolge beibehalten.
quelle