Finden Sie die Summe der nächsten Entfernungen

10

Für diese Aufgabe sollte Ihr Code zwei sortierte Arrays von Ganzzahlen X und Y als Eingabe verwenden. Es sollte die Summe der absoluten Abstände zwischen jeder ganzen Zahl in X und ihrer nächsten Zahl in Y berechnen.

Beispiele:

X = (1 5,9)
Y = (3,4,7)

Der Abstand beträgt 2 + 1 + 2.

X = (1,2,3)
Y = (0,8)

Der Abstand beträgt 1 + 2 + 3.

Ihr Code kann auf jede bequeme Weise eingegeben werden.

Die Haupteinschränkung besteht darin, dass Ihr Code in linearer Zeit in der Summe der Länge der beiden Arrays ausgeführt werden muss. . (Sie können davon ausgehen, dass das Hinzufügen von zwei Ganzzahlen eine konstante Zeit benötigt.)

Anush
quelle
Können wir Listen oder Streams anstelle von Arrays verwenden?
Ad-hoc-Garf-Jäger
@CatWizard Ja, das kannst du!
Anush
1
Wie wird 1 + 2 + 3von X = (1,2,3)und abgeleitet Y = (0,8)?
guest271314
1
@ guest271314 die nächste Nummer zwei jeweils 1, 2und 3in Yheißt 0. So sind die Unterschiede sind 1-0, 2-0, 3-0.
Dylnan
1
@FreezePhoenix da beide Listen sortiert sind , können Sie es in O tun (n + m), weil Sie iterieren Liste , jedes Element zu besuchen einmal, und solange zu verfolgen , das Element Y j am nächsten X i , können Sie Überprüfen Sie gegen Y j und Y j + 1, da einer von denen X i + 1XYjXiYjYj+1Xi+1
Giuseppe

Antworten:

6

Haskell , 70 64 Bytes

a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_<-d,a%c>a%e=x#d|1>0=a%c+b#y
_#_=0

Probieren Sie es online aus!

Erläuterung

Zuerst definieren wir (%)den absoluten Unterschied zwischen zwei Zahlen. Dann definieren wir (#)die interessante Funktion. In der ersten Zeile stimmen wir überein, wenn beide Listen nicht leer sind:

x@(a:b)#(c:d:e)

Bei unserem ersten Fall von hier aus binden wir uns dan e:_mit e:_<-d. Dies stellt sicher, dass des nicht leer ist und setzt sein erstes Element auf e.

Wenn dann das zweite Element von ( ) näher als das erste ( ) am ersten Element von X ( ) liegt, kehren wir zurück, entfernen das erste Element von Y und rufen erneut mit demselben X auf .YecXax#dYX

Wenn wir dem Muster entsprechen, aber die Bedingung nicht erfüllen, tun wir Folgendes:

a%c+b#y

XX

0XY

O(|X|+|Y|)

Haskell , 34 Bytes

O(|X|×|Y|)

x#y=sum[minimum$abs.(z-)<$>y|z<-x]

Probieren Sie es online aus!

Ad-hoc-Garf-Jäger
quelle
Ich habe in der Frage klargestellt, dass wir davon ausgehen können, dass das Hinzufügen von zwei ganzen Zahlen konstante Zeit benötigt.
Anush
2

Python 2 , 124 120 Bytes

X,Y=input()
i=j=s=0
while i<len(X):
 v=abs(Y[j]-X[i])
 if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1
 else:s+=v;i+=1
print s

Probieren Sie es online aus!

Sparte 4 Bytes, indem Sie zu Programm versus Funktion wechseln.

Die Einhaltung der zeitlichen Komplexitätsbeschränkung ist möglich, da beide Listen sortiert sind. Beachten Sie, dass jedes Mal um die Schleife herum entweder iinkrementiert oder jinkrementiert wird. Somit wird die Schleife meistens ausgeführt len(X)+len(Y).

Chas Brown
quelle
Ich habe in der Frage klargestellt, dass das Hinzufügen von zwei ganzen Zahlen eine konstante Zeit in Anspruch nimmt.
Anush
1

C (gcc), 82 Bytes

n;f(x,y,a,b)int*x,*y;{for(n=0;a;)--b&&*x*2-*y>y[1]?++y:(++b,--a,n+=abs(*x++-*y));}

Dies nimmt die Eingabe als zwei ganzzahlige Arrays und ihre Längen (da C sonst keine Möglichkeit hat, ihre Länge zu erhalten). Es kann gezeigt werden, dass dies ausgeführt wird, O(a+b)weil entweder aoder bbei jeder Iteration der Schleife dekrementiert wird, die bei aErreichen endet 0(und bunten nicht dekrementiert werden kann 0).

Probieren Sie es online aus!

n;                     // define sum as an integer
f(x,y,a,b)             // function taking two arrays and two lengths
int*x,*y;              // use k&r style definitions to shorten function declaration
{
 for(n=0;              // initialize sum to 0
 a;)                   // keep looping until x (the first array) runs out
                       // we'll decrement a/b every time we increment x/y respectively
 --b&&                 // if y has ≥1 elements left (b>1, but decrements in-place)...
 *x*2-*y>y[1]?         // ... and x - y > [next y] - x, but rearranged for brevity...
 ++y:                  // increment y (we already decremented b earlier);
 (++b,                 // otherwise, undo the in-place decrement of b from before...
 --a,n+=abs(*x++-*y))  // decrement a instead, add |x-y| to n, and then increment x
;}

Einige Notizen:

  • Anstatt in die Arrays zu indizieren, werden durch Inkrementieren der Zeiger und direktes Dereferenzieren genügend Bytes gespeichert, damit es sich lohnt ( *xvs x[a]und y[1]vs y[b+1]).

  • Die --b&&Bedingung wird auf b>1Umwegen überprüft. Wenn dies der Fall bist 1, wird sie auf Null ausgewertet. Da dies geändert wird b, müssen wir es nicht im ersten Zweig des Ternärs ändern (der voranschreitet y), sondern im zweiten Zweig (der voranschreitet x).

  • Es returnist keine Aussage erforderlich, weil schwarze Magie. (Ich denke , das liegt daran, dass die letzte auszuwertende Anweisung immer der n+=...Ausdruck ist, der dasselbe Register verwendet wie das für Rückgabewerte verwendete.)

Türknauf
quelle
0

Ruby, 88 Bytes

->(p,q){a=q.each_cons(2).map{|a|a.sum/a.size}
x=a[0]
p.sum{|n|x=a.pop if n>x
(n-x).abs}}

Probieren Sie es online aus!

Zum Spaß auch eine kürzere anonyme Funktion, die die Komplexitätsbeschränkungen nicht ganz erfüllt:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}
Tango
quelle
Können Sie in einfachen Worten erklären, wie dieser Code funktioniert? Ich kann nicht sagen, ob es in linearer Zeit läuft.
Anush
2
Dies schlägt den ersten Testfall in der Frage sowie Eingaben wie z [5, 6], [0, 1, 5].
Türknauf
0

JavaScript (Node.js) , 80 Byte

x=>g=(y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?g(y,i+!t,j+t)+!t*(d>0?d:-d):0
  • Es läuft in O (| X | + | Y |): Jede Rekursion läuft in O (1) und es rekursiv | X | + | Y | mal.
    • x, ywerden als Referenz übergeben, die den Inhalt nicht kopieren
  • 1/vist falsch, wenn x[i]außerhalb der Reichweite, sonst wahr
  • t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]ist falsch, solange folgende Bedingungen erfüllt sind. Und was bedeutet, y[j]ist die Zahl, die vin am nächsten isty
    • vist kleiner als (y[j]+y[j+1])/2oder
    • y[j+1]liegt außerhalb des Bereichs, der sich NaNin NaNErtrag umwandeln und mit diesem vergleichen würdefalse
      • Deshalb können wir das >Vorzeichen nicht umdrehen , um 1 weiteres Byte zu sparen
  • tist immer ein boolescher Wert und *konvertiert ihn in 0/ 1vor der Berechnung

Probieren Sie es online aus!

tsh
quelle
0

Mathematica, 40 Bytes

x = {1, 5, 9};
y = {3, 4, 7};

Norm[Flatten[Nearest[y] /@ x] - x]

Wenn Sie ein vollständiges Programm mit Eingaben erstellen müssen:

f[x_,y_]:= Norm[Flatten[Nearest[y] /@ x] - x]

Hier ist der Zeitpunkt für bis zu 1.000.000 Punkte (alle 10.000 abgetastet) für y:

Geben Sie hier die Bildbeschreibung ein

Nahezu linear.

David G. Stork
quelle
1
Diese Antwort ist ein Code-Snippet, da Ihre Eingabe als bereits vorhandene Variablen verwendet wird. Sie sollten es entweder als Unterroutine oder als vollständiges Programm neu formatieren.
Ad-hoc-Garf-Jäger
Ich bin auch ein bisschen misstrauisch, dass dies in linearer Zeit funktioniert. Haben Sie eine Rechtfertigung dafür, warum es so sein sollte? Mathematica ist in der Komplexität seiner Einbauten eher undurchsichtig.
Ad-hoc-Garf-Jäger