Найти сумму ближайших расстояний

10

Для этой задачи ваш код должен принять два отсортированных массива целых чисел X и Y в качестве входных данных. Он должен вычислить сумму абсолютных расстояний между каждым целым числом в X и его ближайшим числом в Y.

Примеры:

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

Расстояние 2 + 1 + 2.

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

Расстояние составляет 1 + 2 + 3.

Ваш код может принимать данные любым удобным для вас способом.

Основным ограничением является то, что ваш код должен выполняться за линейное время в сумме длины двух массивов. , (Можно предположить, что добавление двух целых чисел занимает постоянное время.)

Ануш
источник
Можем ли мы использовать списки или потоки вместо массивов?
Ad Hoc Garf Hunter
@ CatWizard Да, вы можете!
Anush
1
Как 1 + 2 + 3происходит от X = (1,2,3)и Y = (0,8)?
guest271314
1
@ guest271314 ближайший номер два каждый из 1, 2и 3в YИБ 0. Таким образом, различие 1-0, 2-0, 3-0.
Дилнан
1
@FreezePhoenix, так как оба списка отсортированы, вы можете сделать это в O (n + m), потому что вы перебираете список , посещая каждый элемент один раз, и пока вы отслеживаете элемент Y j, ближайший к X i , вы можете проверить против Y j и Y j + 1, так как один из них ближе всего к X i + 1XYjXiYjYj+1Xi+1
Джузеппе

Ответы:

6

Haskell , 70 64 байта

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

Попробуйте онлайн!

объяснение

Сначала мы определяем (%)абсолютную разницу между двумя числами. Затем мы определяем (#)интересную функцию. В первой строке мы сопоставляем, когда оба списка не пусты:

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

На нашем первом случае из здесь мы привязываем dк e:_с e:_<-d. Это гарантирует, что dэто не пусто и устанавливает его первый элемент в e.

Тогда , если второй элемент ( ) ближе , чем первый ( ) к первому элементу X ( ), мы возвращаем удаление первого элемента Y и повторный вызов с тем же X .YecИксax#dYИкс

Если мы сопоставляем шаблон, но не выполняем условие, которое мы выполняем:

a%c+b#y

Что, удаляет первый элемент и добавляет его абсолютную разницу от первого элемента X к оставшемуся результату.ИксИкс

Наконец, если мы не соответствуем шаблону, мы возвращаем . Несоответствие шаблону означает, что X должен быть пустым, потому что Y не может быть пустым.0ИксY

Этот алгоритм имеет обозначение порядка .О(|Икс|+|Y|)

Haskell , 34 байта

Вот как я бы сделал это за время:О(|Икс|×|Y|)

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

Попробуйте онлайн!

Специальный охотник за гарфами
источник
Я уточнил в вопросе, что мы можем предположить, что добавление двух целых чисел занимает постоянное время.
Anush
2

Python 2 , 124 120 байт

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

Попробуйте онлайн!

Сохранено 4 байта при переходе к программе или функции.

Соблюдение ограничения сложности времени возможно, потому что оба списка отсортированы. Обратите внимание, что каждый раз вокруг цикла либо iувеличивается, либо jувеличивается. Таким образом цикл выполняется в большинстве len(X)+len(Y)случаев.

Час Браун
источник
Я уточнил в вопросе, что мы можем предположить, что добавление двух целых чисел занимает постоянное время.
Anush
1

C (gcc), 82 байта

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

Это принимает входные данные в виде двух целочисленных массивов и их длины (поскольку в противном случае C не может получить их длину). Это может быть показано , что работать в O(a+b)потому что либо aили bуменьшается на каждой итерации цикла, который заканчивается , когда aдостигает 0bне может быть уменьшен ниже 0).

Попробуйте онлайн!

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

Некоторые заметки:

  • Вместо индексации в массивах, приращение указателей и разыменование напрямую сохраняет достаточно байтов, чтобы оно того стоило ( *xпротив x[a]и y[1]против y[b+1]).

  • В --b&&проверяет состояние для b>1окольным путем - если bесть 1, то будет нулевое значение. Поскольку это модифицирует b, нам не нужно изменять его в первой ветви троичного (который продвигается y), но нам нужно изменить его обратно во второй (который продвигается x).

  • Никаких returnзаявлений не требуется, потому что черная магия. (Я думаю, это потому, что последним оператором, который будет оцениваться, всегда будет n+=...выражение, которое использует тот же регистр, что и регистр, используемый для возвращаемых значений.)

Дверная ручка
источник
0

Рубин, 88 байт

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

Попробуйте онлайн!

Кроме того, для удовольствия, более короткая анонимная функция, которая не совсем соответствует ограничениям сложности:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}
Танго
источник
Не могли бы вы объяснить простыми словами, как работает этот код? Я не могу сказать, работает ли он за линейное время.
Anush
2
Это не проходит первый тестовый пример в вопросе, а также входные данные, такие как [5, 6], [0, 1, 5].
Ручка двери
0

JavaScript (Node.js) , 80 байт

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
  • Он запускается в O (| X | + | Y |): каждая рекурсия запускается в O (1) и рекурсивна | X | + | Y | раз.
    • x, yпередаются по ссылке, которые не копируют содержимое
  • 1/vявляется ложным, если x[i]находится вне диапазона, правда в противном случае
  • t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]ложно, если выполняются следующие условия. А это означает y[j], что число является ближайшим к vвy
    • vменьше (y[j]+y[j+1])/2или
    • y[j+1]находится вне диапазона, который будет преобразован в NaNи сравнить с NaNдоходностьюfalse
      • вот почему мы не можем перевернуть >знак, чтобы сохранить еще 1 байт
  • t всегда логическое значение, и * преобразовать его в 0/ 1перед вычислением

Попробуйте онлайн!

ТТГ
источник
0

Mathematica, 40 байт

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

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

Если вы должны создать полную программу, с входами:

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

Вот время до 1000000 точек (выборка каждые 10000) для y:

введите описание изображения здесь

Близко к линейному.

Аист аист
источник
1
Этот ответ является фрагментом кода, так как ваш ввод воспринимается как уже существующие переменные. Вы должны переформатировать это, чтобы быть или подпрограммой или полной программой.
Специальный охотник за
Я также немного подозреваю, что это работает в линейное время, есть ли у вас обоснование, почему это должно? Mathematica имеет тенденцию быть довольно непрозрачным по сложности своих встроенных функций.
Ad Hoc Garf Hunter