W tym celu kod powinien przyjmować dwie posortowane tablice liczb całkowitych X i Y jako dane wejściowe. Powinien obliczyć sumę bezwzględnych odległości między każdą liczbą całkowitą w X i jej najbliższą liczbą w Y.

Przykłady:

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

Odległość wynosi 2 + 1 + 2.

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

Odległość wynosi 1 + 2 + 3.

Twój kod może pobierać dane w dowolny dogodny sposób.

Głównym ograniczeniem jest to, że kod musi działać w czasie liniowym w sumie długości dwóch tablic. . (Możesz założyć, że dodanie dwóch liczb całkowitych wymaga stałego czasu).

Haskell , 70 64 bajtów

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

Wypróbuj online!

Wyjaśnienie

Najpierw określamy (%)bezwzględną różnicę między dwiema liczbami. Następnie określamy, (#)że jest to interesująca funkcja. W pierwszym wierszu dopasowujemy, gdy obie listy nie są puste:

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

W naszym pierwszym przypadku stąd wiążemy dsię e:_z e:_<-d. Zapewnia dto, że nie jest pusty i ustawia jego pierwszy element e.

Następnie, jeśli drugi element ( ) jest bliżej niż pierwszy ( ) do pierwszego elementu X ( ), wracamy usuwanie pierwszego elementu Y i dzwoni ponownie z tym samym X .$Y$ec$X$ax#d$Y$$X$

Jeśli dopasujemy wzór, ale nie spełnimy warunku, to:

a%c+b#y

$X$$X$

$0$$X$$Y$

$O(|X|+|Y|)$

Haskell , 34 bajty

$O(\left|X\right|\times\left|Y\right|)$

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

Wypróbuj online!

Python 2 , 124 120 bajtów

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

Wypróbuj online!

Zaoszczędzono 4 bajty, przechodząc do programu kontra funkcja.

Spełnienie ograniczenia złożoności czasowej jest możliwe, ponieważ obie listy są posortowane. Zauważ, że za każdym razem wokół pętli albo ijest zwiększana, albo jjest zwiększana. Zatem pętla jest wykonywana przez większość len(X)+len(Y)czasu.

C (gcc), 82 bajty

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));}

Pobiera to dane wejściowe jako dwie tablice liczb całkowitych i ich długości (ponieważ C nie ma innego sposobu na uzyskanie ich długości). Można to wykazać, prowadzony w O(a+b), ponieważ albo aczy bjest zmniejszana w każdej iteracji pętli, który kończy się, gdy aosiągnie 0(i bnie może być zmniejszony poniżej 0).

Wypróbuj online!

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
;}

Niektóre uwagi:

• Zamiast indeksować do tablic, zwiększanie wskaźników i dereferencjonowanie bezpośrednio zapisuje wystarczającą liczbę bajtów, aby było warto ( *xvs x[a]i y[1]vs y[b+1]).

• Do --b&&kontroli stanu dla b>1okrężną drogą - jeśli bjest 1, to będzie ocenić na zero. Ponieważ to się zmienia b, nie musimy go zmieniać w pierwszej gałęzi trójki (która się przesuwa y), ale musimy to zmienić w drugiej (która się przesuwa x).

• Żadne returnoświadczenie nie jest potrzebne, ponieważ czarna magia. (Myślę , że dzieje się tak, ponieważ ostatnią ocenianą instrukcją będzie zawsze n+=...wyrażenie, które używa tego samego rejestru, co rejestr zwracanych wartości.)

Rubinowy, 88 bajtów

->(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}}

Wypróbuj online!

Ponadto, dla zabawy, krótsza anonimowa funkcja, która nie do końca spełnia ograniczenia dotyczące złożoności:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}

JavaScript (Node.js) , 80 bajtów

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

• Działa w O (| X | + | Y |): Każda rekurencja przebiega w O (1) i rekurencyjne | X | + | Y | czasy.
  • x, ysą przekazywane przez odniesienie, które nie kopiują treści
• 1/vjest fałszem, jeśli x[i]jest poza zasięgiem, prawdę mówiąc inaczej
• t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]jest fałszem, o ile spełnione są następujące warunki. I środki, które y[j]oznacza liczbę najbliżej vwy
  • vjest mniejsza niż (y[j]+y[j+1])/2lub
  • y[j+1]jest poza zakresem, co można przeliczyć na NaNi porównać z NaNwydajnościąfalse
    • dlatego nie możemy odwrócić >znaku, aby zaoszczędzić jeszcze 1 bajt
• tjest zawsze wartością logiczną i *konwertuje ją na 0/ 1przed obliczeniem

Wypróbuj online!

Mathematica, 40 bajtów

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

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

Jeśli musisz utworzyć pełny program z danymi wejściowymi:

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

Oto czas do 1 000 000 punktów (próbkowanych co 10 000) dla y:

Blisko do liniowego.