Encuentra la suma de las distancias más cercanas

10

Para esta tarea, su código debe tomar dos matrices ordenadas de enteros X e Y como entrada. Debe calcular la suma de las distancias absolutas entre cada número entero en X y su número más cercano en Y.

Ejemplos:

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

La distancia es 2 + 1 + 2.

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

La distancia es 1 + 2 + 3.

Su código puede recibir información de cualquier manera que sea conveniente.

La restricción principal es que su código debe ejecutarse en tiempo lineal en la suma de la longitud de las dos matrices. . (Puede suponer que agregar dos enteros lleva tiempo constante).

Anush
fuente
¿Podemos usar listas o secuencias en lugar de matrices?
Ad Hoc Garf Hunter
@ CatWizard ¡Sí puedes!
Anush
1
¿Cómo se 1 + 2 + 3deriva de X = (1,2,3)y Y = (0,8)?
guest271314
1
@ guest271314 el más cercano número dos de cada 1, 2y 3en YIS 0. Por lo tanto, las diferencias son 1-0, 2-0, 3-0.
dylnan 01 de
1
@FreezePhoenix ya que ambas listas están ordenadas, puede hacerlo en O (n + m), porque itera sobre la lista , visitando cada elemento una vez, y siempre y cuando realice un seguimiento del elemento Y j más cercano a X i , puede coteje con Y j y Y j + 1 ya que uno de ellos está más cerca de X i + 1XYjXyoYjYj+1Xyo+1
Giuseppe

Respuestas:

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

Pruébalo en línea!

Explicación

Primero definimos (%)como la diferencia absoluta entre dos números. Luego definimos (#)ser la función interesante. En la primera línea, coincidimos cuando ambas listas no están vacías:

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

En nuestro primer caso de aquí nos atamos da e:_con e:_<-d. Esto asegura que dno esté vacío y establece su primer elemento e.

Entonces, si el segundo elemento de ( ) está más cerca que la primera ( ) al primer elemento de X ( ), volvemos retirar el primer elemento de Y y llamar de nuevo con la misma X .YecXax#dYX

Si hacemos coincidir el patrón pero no pasamos la condición que hacemos:

a%c+b#y

Lo cual elimina el primer elemento de y agrega la diferencia absoluta del primer elemento de X al resultado restante.XX

Finalmente, si no coincidimos con el patrón, devolvemos . No coincidir con el patrón significa que X debe estar vacío porque Y no puede estar vacío.0 0XY

Este algoritmo tiene notación de orden .O(El |XEl |+El |YEl |)

Haskell , 34 bytes

Así es como lo haría en tiempo :O(El |XEl |×El |YEl |)

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

Pruébalo en línea!

Ad Hoc Garf Hunter
fuente
Aclaré en la pregunta que podemos suponer que agregar dos enteros lleva tiempo constante.
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

Pruébalo en línea!

Se guardaron 4 bytes moviéndose al programa versus la función.

Es posible cumplir con la restricción de complejidad de tiempo porque ambas listas están ordenadas. Tenga en cuenta que cada vez alrededor del ciclo, ise incrementa o jse incrementa. Por lo tanto, el bucle se ejecuta en la mayoría de los len(X)+len(Y)casos.

Chas Brown
fuente
Aclaré en la pregunta que podemos suponer que agregar dos enteros lleva tiempo constante.
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));}

Esto toma la entrada como dos matrices enteras y sus longitudes (ya que C no tiene forma de obtener su longitud de otra manera). Se puede mostrar que se ejecuta O(a+b)porque ao bse disminuye en cada iteración del bucle, que termina cuando allega 0(y bno se puede disminuir a continuación 0).

Pruébalo en línea!

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

Algunas notas:

  • En lugar de indexar en las matrices, el incremento de los punteros y la eliminación de referencias directamente ahorra suficientes bytes para que valga la pena ( *xvs x[a]y y[1]vs y[b+1]).

  • La --b&&condición se verifica de b>1forma indirecta; si bes así 1, se evaluará a cero. Como esto se modifica b, no necesitamos cambiarlo en la primera rama del ternario (que avanza y), pero sí necesitamos volver a cambiarlo en la segunda (que avanza x).

  • No returnse necesita ninguna declaración, porque la magia negra. (Creo que se debe a que la última declaración que se evaluará siempre será la n+=...expresión, que usa el mismo registro que el utilizado para los valores de retorno).

Pomo de la puerta
fuente
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}}

Pruébalo en línea!

Además, por diversión, una función anónima más corta que no cumple con las restricciones de complejidad:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}
Tango
fuente
¿Podría explicar en términos simples cómo funciona este código? No puedo decir si se ejecuta en tiempo lineal.
Anush
2
Esto falla el primer caso de prueba en la pregunta, así como entradas como [5, 6], [0, 1, 5].
Pomo de la puerta
0

JavaScript (Node.js) , 80 bytes

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
  • Se ejecuta en O (| X | + | Y |): cada recursión se ejecuta en O (1), y es recursiva | X | + | Y | veces.
    • x, yse pasan por referencia, que no copian el contenido
  • 1/ves falso si x[i]está fuera de rango, de lo contrario es cierto
  • t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]es falso siempre que se cumplan las siguientes condiciones. Y lo que significa y[j]es el número más cercano a veny
    • ves menor (y[j]+y[j+1])/2o
    • y[j+1]está fuera de rango, lo que convertiría NaNy compararía con el NaNrendimientofalse
      • es por eso que no podemos voltear el >signo para guardar 1 byte más
  • tsiempre es un valor booleano y *conviértalo a 0/ 1antes de calcular

Pruébalo en línea!

tsh
fuente
0

Mathematica, 40 bytes

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

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

Si debe crear un programa completo, con entradas:

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

Aquí está el tiempo para hasta 1,000,000 de puntos (muestreados cada 10,000) para y:

ingrese la descripción de la imagen aquí

Cercano a lineal.

David G. Stork
fuente
1
Esta respuesta es un fragmento de código ya que su entrada se toma como variables preexistentes. Debe reformatearlo para que sea una subrutina o un programa completo.
Ad Hoc Garf Hunter
También sospecho un poco que esto funcione en tiempo lineal, ¿tiene alguna justificación de por qué debería hacerlo? Mathematica tiende a ser bastante opaco en la complejidad de sus componentes integrados.
Ad Hoc Garf Hunter