Найти все возможные расстояния от двух массивов

Question

Для двух отсортированных массивов A и B длина N. Каждый элемент может содержать натуральное число меньше M. Определите все возможные расстояния для всех комбинаций элементов A и B. В этом случае, если A[i] - B[j] < 0, то расстояние M + (A[i] - B[j]).

Пример:

A = {0,2,3} 
B = {1,2} 
M = 5 

Distances = {0,1,2,3,4} 

Примечание: Я знаю O(N^2) решение, но мне нужно быстрее, чем решение O(N^2) и O(N x M).

Редактировать: Array A, B и Distances содержат отдельные элементы.

Answer 1

Вы можете получить решение сложности O (MlogM) следующим образом.

1. Подготовить Ax массив длины M с Ах [I] = 1, если я принадлежит А (и 0 в противном случае)
2. Подготовить массив Bx длины M с Bx [М-1-я] = 1, если я принадлежу в (и 0 в противном случае)
3. с помощью быстрого преобразования Фурье, чтобы свертка этих 2 последовательности вместе
4. Проверьте выходной массив, отличные от нуля значений соответствуют возможным расстояниям

Обратите внимание, что FFT обычно выполняется с номерами с плавающей запятой, поэтому в ste p 4, вы, вероятно, захотите проверить, превышает ли выход более 0,5, чтобы избежать возможных проблем с шумом округления.

Answer 2

I возможно сделано с оптимизированным N * N.

Если преобразовать в 0 и 1, где 1 массив на позиции, которые присутствуют в А (в диапазоне [0..M]. После того, как преобразовать этот массив в битмаски, размер массива будет уменьшился в 64 раза.

Это позволит результатам вставки блоков размера 64. сложности еще будет N*N, но рабочее время будет значительно уменьшено. Как упоминалось ограничение автора 50000 для A и B размеров и M. Ожидаемых операции будут рассчитывать N * N/64 ~ = 4 * 10^7. Пройдет через 1 сек.

Answer 3

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

Инициализировать два битвектора длины M. Назовите эти vectA и vectAnswer. Установите биты vectA, соответствующие элементам в A. Оставьте vectAnswer со всеми нулями.

Определите способ поворота битвектора на k элементов (поверните вниз). Я назову это вращением (vect, k).

Затем для каждого элемента b из B, vectAnswer = vectAnswer | поворота (Vecta, б).