Znajdź sumę najbliższych odległości

10

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).

Anush
źródło
Czy możemy używać list lub strumieni zamiast tablic?
Ad Hoc Garf Hunter
@CatWizard Tak, możesz!
Anush
1
Jak to 1 + 2 + 3pochodzi od X = (1,2,3)a Y = (0,8)?
guest271314,
1
@ guest271314 najbliższy numer dwa każda 1, 2oraz 3w YIs 0. Tak więc różnice są 1-0, 2-0, 3-0.
dylnan
1
@FreezePhoenix, ponieważ obie listy są posortowane, możesz to zrobić w O (n + m), ponieważ wykonujesz iterację po liście , odwiedzając każdy element jeden raz i tak długo, jak śledzisz element Y j najbliższy X i , możesz sprawdzić przed Y j i Y j + 1, ponieważ jeden z nich jest najbliżej X i + 1XYjXiYjYj+1Xi+1
Giuseppe

Odpowiedzi:

6

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 .YecXax#dYX

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

a%c+b#y

XX

0XY

O(|X|+|Y|)

Haskell , 34 bajty

O(|X|×|Y|)

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

Wypróbuj online!

Ad Hoc Garf Hunter
źródło
Wyjaśniłem w pytaniu, że możemy założyć, że dodanie dwóch liczb całkowitych wymaga stałego czasu.
Anush,
2

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.

Chas Brown
źródło
Wyjaśniłem w pytaniu, że możemy założyć, że dodanie dwóch liczb całkowitych zajmuje cały czas.
Anush,
1

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.)

Klamka
źródło
0

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}
Tango
źródło
Czy możesz wyjaśnić w prosty sposób, jak działa ten kod? Nie wiem, czy działa w czasie liniowym.
Anush
2
Nie powiedzie się to w pierwszym przypadku testowym w pytaniu, a także danych wejściowych takich jak [5, 6], [0, 1, 5].
Klamka
0

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!

tsh
źródło
0

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:

wprowadź opis zdjęcia tutaj

Blisko do liniowego.

David G. Stork
źródło
1
Ta odpowiedź jest fragmentem kodu, ponieważ dane wejściowe są traktowane jako istniejące wcześniej zmienne. Powinieneś sformatować go jako podprogram lub pełny program.
Ad Hoc Garf Hunter
Jestem też trochę podejrzliwy, że to działa w czasie liniowym, czy masz jakieś uzasadnienie, dlaczego tak powinno być? Matematyka jest raczej nieprzejrzysta w złożoności swoich wbudowanych funkcji.
Ad Hoc Garf Hunter