Encontre a soma das distâncias mais próximas

10

Para esta tarefa, seu código deve receber duas matrizes classificadas de números inteiros X e Y como entrada. Ele deve calcular a soma das distâncias absolutas entre cada número inteiro em X e o número mais próximo em Y.

Exemplos:

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

A distância é 2 + 1 + 2.

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

A distância é 1 + 2 + 3.

Seu código pode receber entradas da maneira que for conveniente.

A principal restrição é que seu código deve ser executado em tempo linear na soma do comprimento das duas matrizes. . (Você pode assumir que a adição de dois números inteiros leva tempo constante.)

Anush
fonte
Podemos usar listas ou fluxos em vez de matrizes?
Ad Hoc Garf Hunter
@ CatWizard Sim, você pode!
Anush
11
Como é 1 + 2 + 3derivado X = (1,2,3)e Y = (0,8)?
precisa saber é o seguinte
11
@ guest271314 o número mais próximo dois cada um 1, 2e, 3em Yé 0. Assim, as diferenças são 1-0, 2-0, 3-0.
#
11
@FreezePhoenix, uma vez que as duas listas são classificadas, você pode fazê-lo em O (n + m), porque você itera sobre a lista , visitando cada elemento uma vez e enquanto acompanha o elemento mais próximo de , pode verificar e uma vez que um dos que é mais próximo deY j X i Y j Y j + 1 X i + 1XYjXiYjYj+1Xi+1
Giuseppe

Respostas:

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

Experimente online!

Explicação

Primeiro, definimos (%)como a diferença absoluta entre dois números. Então, definimos (#)como a função interessante. Na primeira linha, correspondemos quando as duas listas não estão vazias:

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

Em nosso primeiro caso a partir daqui que se ligam da e:_com e:_<-d. Isso garante que dnão esteja vazio e define seu primeiro elemento e.

Então, se o segundo elemento de ( ) é mais estreita do que a primeira ( ) para o primeiro elemento de ( ), voltamos a remoção do primeiro elemento de e ligando de novo com o mesmo .X Y XYecXax#dYX

Se correspondermos ao padrão, mas não passarmos a condição, fazemos:

a%c+b#y

O qual remove o primeiro item de e adiciona a diferença absoluta do primeiro elemento de ao resultado restante.XXX

Por fim, se não correspondermos ao padrão, retornamos . Não corresponder ao padrão significa que deve estar vazio porque não pode estar vazio.X Y0XY

Este algoritmo possui notação de ordem .O(|X|+|Y|)

Haskell , 34 bytes

Aqui está como eu faria isso no tempo :O(|X|×|Y|)

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

Experimente online!

Caçador Ad Hoc Garf
fonte
Esclarei na pergunta que podemos assumir que a adição de dois números inteiros leva tempo 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

Experimente online!

Salva 4 bytes movendo-se para programa versus função.

É possível atender à restrição de complexidade de tempo porque as duas listas são classificadas. Observe que toda vez que o loop ié incrementado ou jincrementado. Assim, o loop é executado na maioria das len(X)+len(Y)vezes.

Chas Brown
fonte
Esclareci na pergunta que podemos assumir que a adição de dois números inteiros leva tempo 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));}

Isso recebe a entrada como duas matrizes inteiras e seus comprimentos (já que C não tem como obter seu comprimento). Isso pode ser mostrado para executar O(a+b)porque aou bé diminuído em cada iteração do loop, que termina quando aatinge 0(e bnão pode ser diminuído abaixo 0).

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

Algumas notas:

  • Em vez de indexar nas matrizes, incrementar os ponteiros e desreferenciar diretamente economiza bytes suficientes para que valha a pena ( *xvs x[a]e y[1]vs y[b+1]).

  • A --b&&condição verifica de b>1maneira indireta - se bfor 1, ela será avaliada como zero. Como isso modifica b, não precisamos alterá-lo no primeiro ramo do ternário (que avança y), mas precisamos alterá-lo novamente no segundo (que avança x).

  • Nenhuma returndeclaração é necessária, porque a magia negra. ( Acho que é porque a última instrução a ser avaliada sempre será a n+=...expressão, que usa o mesmo registro que o usado para valores de retorno.)

Maçaneta da porta
fonte
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}}

Experimente online!

Além disso, por diversão, uma função anônima mais curta que não atende às restrições de complexidade:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}
Tango
fonte
Você poderia explicar em termos simples como esse código funciona? Não sei dizer se funciona em tempo linear.
Anush
2
Isso falha no primeiro caso de teste da pergunta, bem como em entradas como [5, 6], [0, 1, 5].
Maçaneta
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
  • É executado em O (| X | + | Y |): Toda recursão é executada em O (1) e é recursiva | X | + | Y | vezes.
    • x, ysão passados ​​por referência, que não copiam o conteúdo
  • 1/vé falso se x[i]estiver fora de alcance, de outra forma
  • t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]é falso desde que as seguintes condições sejam atendidas. E que meios y[j]é o número mais próximo vnay
    • vé menor que (y[j]+y[j+1])/2, ou
    • y[j+1]está fora do intervalo, que seria convertido em NaNe comparado com o NaNrendimentofalse
      • é por isso que não podemos virar o >cartaz para economizar mais 1 byte
  • té sempre um valor booleano e *converte-o para 0/ 1antes de calcular

Experimente online!

tsh
fonte
0

Mathematica, 40 bytes

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

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

Se você deve criar um programa completo, com entradas:

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

Aqui está o momento para até 1.000.000 de pontos (amostrados a cada 10.000) para y:

insira a descrição da imagem aqui

Perto de linear.

David G. Stork
fonte
11
Esta resposta é um trecho de código, pois sua entrada é considerada como variáveis ​​pré-existentes. Você deve reformatá-lo para ser uma sub-rotina ou um programa completo.
Ad Hoc Garf Hunter
Também estou um pouco desconfiado de que isso funcione em tempo linear. Você tem alguma justificativa para o porquê disso? O Mathematica tende a ser bastante opaco na complexidade de seus componentes.
Ad Hoc Garf Hunter