Найти ближайшие элементы через несколько массивов

Question

Say У меня есть два массива:

a=[10 21 50 70 100 120]; 
b=[18 91]; 

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

Результат:

idxa=[1 2 3 4 5 6] 

idxb=[2 5] 

где согласующие элементы одни и те же числа.

Я смущен, потому что я не уверен, как обеспечить (например), что 18 совпадений с 21 вместо 10, потому что они оба соответствуют требованиям быть в пределах 10 единиц друг от друга. Кроме того, я хотел бы сделать это через несколько (до 8) списков, и код становится чрезмерно сложным, и я чувствую, что есть простое решение, которое мне не хватает. Я не беспокоюсь об эффективности, потому что длины списков малы.

Спасибо!

Answer 1

Ваши массивы, кажется, отсортированы (я собираюсь продолжить это предположение, а если нет, вы можете просто отсортировать их).

Вы пытались объединить несколько массивов в один массив? (Подобно шагу слияния сортировки слияния). Это было бы хорошей отправной точкой, так как это уменьшит вашу проблему до «Найти элемент шкафа в массиве», что тривиально в сравнении.

Это также позволит удалить дубликаты; т.е. уменьшить все «21» до одного «21» в массиве.

Для того, чтобы 18 соответствовали 21 вместо 10, вы хотели бы рассчитать разницу между вашим ключом (18) и каждым значением в пределах 10 единиц ([10,21)), а затем выбрать тот, который имеет наименьшую разницу ,

ОБНОВЛЕНИЕ: В ответ на ваши комментарии о поиске значений, общих для всех массивов, это можно сделать при слиянии массивов путем нахождения пересечения массивов, что может быть предопределенным способом в зависимости от вашего языка.

Answer 2

Для небольших массивов это может быть сделано с помощью грубой силы:

(1) Итерация меньшего из двух массивов, то большего массива
(2) Следите за «Ближайший матч So Far» CMSF
(3) Если вы найдете лучший матч, обновить CMSF
(4) Когда вы дойдете до конца списка, если CMSF является < = 10 держать его, в противном случае игнорировать этот элемент (не имеющий аналогов)