Каким алгоритмом заменить перебор 3 массивов
Задача: Вводится число n, затем вводятся последовательно 3 массива длинной n, числа в которых идут в порядке возрастания. Нужно найти такую тройку чисел (каждое число из отдельного массива), чтобы разность между максимальным и минимальным из трёх чисел была минимальной.
Пример 1:
Ввод:
3
2 3 100
1 100 200
1 200 300
Вывод:
1
(т.е. среди всех возможных троек у тройки 2 1 1 самая минимальная разность между максимальным элементом (2) и минимальным (1)).
Пример 2:
Ввод:
5
2 38 45 267 499
80 90 91 105 200
13 24 76 133 351
Вывод:
35
(Здесь среди всех возможных троек у тройки 45 80 76 самая минимальная разность между максимальным элементом (80) и минимальным (45)).
Перебором задачу решать долго - сложность получается O(n^3). Подскажите, пожалуйста, может существует алгоритм, позволяющий решить задачу без перебора? Я прошу только алгоритм, помогите, пожалуйста!
Ответы (1 шт):
За O(n):
- Храните три индекса, изначально - 0, 0, 0.
- Проверяете тройку, соотвествующую этим индексам (т.е. сначала - тройку из первых элементов каждого массива).
- Находите минимальный элемент из тройки, и соответсвующий индекс увеличиваете на 1 (если только индекс уже не показывает на последний элемент - тогда берете следующий по мелкости).
- Повторяете эти два шага, пока не дойдете до тройки из последних элементов.