Конечно, решение полного брутфорса, описанное IVlad, простое и, следовательно, его легче и быстрее писать, но его сложность составляет O(n3).
В соответствии с вашим тегом algorithm я хотел бы опубликовать более сложный алгоритм, который имеет O(n2) худший случай и O(nlogn) среднюю сложность (почти уверен в этом, но я слишком ленив, чтобы сделать доказательство).
Описание алгоритма
Подумайте о некотором абстрактном (X, Y, Z) кортеже. Мы хотим найти кортеж с минимальным расстоянием между его максимальным и минимальным элементом. На данный момент мы можем сказать, что distance фактически создается нашим максимальным элементом и минимальным элементом. Следовательно, значение элемента между ними действительно не имеет значения, если оно действительно лежит между максимумом и минимумом.
Итак, вот подход. Мы выделяем некоторый дополнительный набор (назовем его S) и объединяем каждый начальный набор (X, Y, Z) в один. Нам также нужна возможность поиска начального набора каждого элемента в только что созданном наборе (поэтому, если мы укажем на какой-то элемент в S, скажем, S[10] и спросим «Откуда этот парень?» , наше приложение должно ответить примерно так: «Он приходит от Y).
После этого давайте отсортируем наш новый набор S по ключам (в некоторых случаях это будет O (n log n) или O (n))
Определение минимального расстояния
Теперь интересная часть приходит. Мы хотим вычислить искусственное значение, назовем его минимальное расстояние и отметим его как d[x], где x - некоторый элемент из S. Это значение относится к минимальному расстоянию max - min, которое может быть достигнуто с использованием элементов, которые являются предшественниками / преемниками текущего элемента в последовательности.
Рассмотрим следующий пример - это наш S набор (первая строка показывает индексы, вторая - значения и буквы X, Y и Z относятся к исходным наборам):
0 1 2 3 4 5 6 7
------------------
1 2 4 5 8 10 11 12
Y Z Y X Y Y X Z
Допустим, мы хотим вычислить, что наше минимальное расстояние для элемента с индексом 4. Фактически, это минимальное расстояние означает best (x, y, z) кортеж который может быть построен с использованием выбранного элемента.
В нашем случае (S[4]) мы можем сказать, что наша пара (x, y, z) определенно будет выглядеть как (something, 8, something), потому что в ней должен быть элемент, для которого мы рассчитываем расстояние (довольно очевидно, хе-хе).
Теперь мы должны заполнить пробелы. Мы знаем, что элементы, которые мы ищем, должны быть от X и Z. И мы хотим, чтобы эти элементы были лучшими с точки зрения расстояния max - min. Существует простой способ их выбора.
Мы выполняем двунаправленный прогон (прогон влево, прогон вправо от текущего элемента) в поисках первого элемента, а не из-Y. В этом случае мы будем искать два ближайших элемента из X и Z в двух направлениях (всего 4 элемента).
Этот метод поиска нам нужен: если мы выберем первый элемент из X во время работы (влево / вправо, не имеет значения), этот элемент подойдет нам лучше, чем любой другой элемент, который следует за ним с точки зрения расстояния. Это происходит потому, что наш набор S отсортирован.
В случае моего примера (считая расстояние для элемента с индексом 4) мы пометили бы элементы с индексами 6 и 7 как подходящие с правой стороны и элементы с индексами 1 и 3 с левой стороны.
Теперь нам нужно протестировать 4 случая, которые могут произойти, - и взять случай, чтобы наше расстояние было минимальным. В нашем конкретном случае мы имеем следующее (элементы, возвращаемые предыдущей подпрограммой):
Z X Y X Z
2 5 8 11 12
Мы должны проверить каждый (X, Y, Z) кортеж, который может быть построен с использованием этих элементов, взять кортеж с минимальным расстоянием и сохранить это расстояние для нашего элемента. В этом примере мы сказали бы, что кортеж (11, 8, 12) имеет лучшее расстояние 4. Итак, мы храним d[5] = 4 (5 здесь индекс элемента) .
Сдача результата
Теперь, когда мы знаем, как найти расстояние, давайте сделаем это для каждого элемента в нашем наборе S (, эта операция займет O(n2) в худшем случае и в лучшее время - что-то вроде O(nlogn) в среднем).
После того, как у нас будет значение расстояния для каждого элемента в нашем наборе, просто выберите элемент с минимальным расстоянием и запустите подсчет расстояний * Алгоритм 1127 * (который описан выше) для него еще раз, но теперь сохраните кортеж (-, -, -). Это был бы ответ.
псевдокод
Вот псевдокод, я пытался упростить его чтение, но его реализация была бы более сложной, потому что вам нужно будет кодировать наборы поиска * ("определить набор для элемента"). Также обратите внимание, что процедуры определения кортежа и определения расстояния в основном совпадают, но вторая дает фактический кортеж.
COMBINE (X, Y, Z) -> S
SORT(S)
FOREACH (v in S)
DETERMINE_DISTANCE(v, S) -> d[v]
DETERMINE_TUPLE(MIN(d[v]))
P.S
Я почти уверен, что этот метод может быть легко использован для (-, -, -, ... -) поиска кортежей, что все еще приводит к хорошей алгоритмической сложности.