Найти кратчайшее расстояние между двумя группами чисел

Создайте битовый вектор из 10 ^ 5 элементов для каждого сегмента. Следите за минимальным расстоянием (первоначально 10 ^ 5, пока оба ковша не будут пустыми).

Теперь предположим, что вы добавляете элемент x в одну из групп. Сделайте следующее:

1. Set the bit x of the same bucket.
2. Check whether the other bitvector has any set elements within min_distance-1 of x
3. Update min_distance as appropriate

Время выполнения: при вставке это O (min_distance), что технически равно O (1), так как min_distance ограничен. При опросе это O (1), так как вы просто возвращаете min_distance.

редактировать Если элементы не ограничены 10 ^ 5, а просто расстоянием между минимумом и максимумом, это нужно будет изменить, но все равно будет работать. Я могу подробно описать необходимые изменения, если это имеет значение.

Вставьте свои ведра в две Y-быстрые попытки (https://en.wikipedia.org/wiki/Y-fast_trie). Поиск ближайшего преемника или предшественника O(log log M), где M это диапазон (на самом деле это максимальный элемент, но мы можем сместить), который в вашем случае будет ограничен примерно четырьмя операциями.

Поскольку вы будете хранить ближайшую разницу, поиск будет O(1) (если вы не получаете полные корзины каждый раз, а не постоянно обновляете), тогда как вставка, удаление и обновление для каждого элемента будут O(log log M),

Вот моя попытка: отсортировать каждое ведро, затем сортировать их, отслеживая минимальное расстояние по пути: O(n+2.n/2.ln(n/2)) = O(n.ln(n)):

sort buk1
sort buk2
min = INT_MAX
last = some value
do
if top(buk1) > top(buk2)
min = min(min, abs(top(buk1) - last))
last = top(buk1)
pop(buk1)
else
min = min(min, abs(top(buk2) - last))
last = top(buk2)
pop(buk2)
while !empty(buk1) and !empty(buk2)

O (1), конечно, невозможно.

Какой-то псевдокод, который я бы использовал в качестве отправной точки:

sort(B1)
sort(B2)

i1 = 0
i2 = 0

mindist = MAX_INT

// when one of the buckets is empty, we'll simply return MAX_INT.
while(i1 < B1.size() && i2 < B2.size())
t = B1[i1] - B2[i2]
mindist = min(mindist, abs(t))
if t > 0
i2 ++
else
i1 ++

return mindist

По крайней мере, это O (n log n), потому что в нем преобладает сортировка в начале. Если ваши ведра уже отсортированы, вы можете иметь O (n).

Редактировать:

После новой информации о том, что элементы почти отсортированы, я бы предложил на самом деле отсортировать их при вставке. Сортировка вставок с бинарным поиском — не лучший вариант для этой ситуации. Просто добавьте новый элемент и поменяйте его местами, пока он не уместится. Обычно это не будут свопы, и для 1%, где вам нужны свопы, в 99% случаев это будет только один. В худшем случае сложность составляет O (n), но среднее значение будет почти O (1).

Если вы считаете, чтобы рассчитать mindist для всех пар ведер вам нужно хранить i1 а также i2 а также mindist, Скажем B1 это ведро, где вы добавляете новый элемент. Вы сортируете это и уменьшаете i2 пока не будет 0 или же B2[i2] < B1[i1], Поскольку элементы являются метками времени, большую часть времени это будет не более одного шага. Затем вы снова запускаете цикл while, который обычно также будет состоять из одного шага. Таким образом, вычислительная сложность O (k) для k сегментов, а сложность памяти O (k ^ 2).

Мне нравится идея Дэйва Гэлвина, слегка модифицированная:

Пусть maxV будет максимальным количеством элементов maxV = max (bucket1.size, bucket2.size)

1. Создайте два массива, каждый из которых имеет размер maxV. Заполните их:

for (j=0 to bucket1.size)
array1(bucket1(j)) = bucket1(j)
for (j=0 to bucket2.size)
array2(bucket2(j)) = bucket1(j)

Массивы теперь отсортированы. Остальные элементы в массивах равны 0.

2. Теперь используйте два итератора, по одному для каждого массива:

it1 = array1.begin
it2 = array2.begin
while (it1 == 0)
++it1
while (it2 == 0)
++it2
minDist = abs(it1-it2)
while (it1 != array1.end && it2 != array2.end)
{   //advance until overpass the other
while (it1 <= it2 && it1 != array1.end)
++it1
if (it1 > 0)
check minDist between it1, it2
while (it2 <= it1 && it2 != array2.end)
++it2
if (it2 > 0)
check minDist between it1, it2
if (it1 = it2)
//well, minDist = 0
return now
}

Шаг 1 — это O (n). Шаг 2 также O (n). Я не знаю, является ли это более эффективным или нет, чем сортировка ведер для больших или коротких ведер.

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

Это дает O (1) поиск.