Описание проблемы:
Существует 3 массива A, B, C, заполненные положительными целыми числами, и все три массива имеют одинаковый размер.
Найти min (| a-b | + | b-c | + | c-a |), где a находится в A, b находится в B, c находится в C.
Я работал над проблемой весь уик-энд. Друг сказал мне, что это можно сделать в линейном времени. Я не понимаю, как это возможно.
Как вы это сделаете?
Ну, я думаю, что могу сделать это в O (n log n). Я могу делать только O (n), если массивы первоначально отсортированы.
Во-первых, обратите внимание, что вы можете переставлять a, b, c, как вам нравится, без изменения значения выражения. Итак, пусть x будет наименьшим из a, b, c; пусть y - середина трех; и пусть z - максимум. Тогда заметим, что выражение просто равно 2*(z-x). (Изменить: это легко увидеть... Когда у вас есть три числа в порядке, x < y < z, сумма равна (y-x) + (z-y) + (z-x), которая равна 2*(z-x))
Таким образом, все, что мы действительно пытаемся сделать, это найти три числа, так что внешние два максимально близки друг к другу, а другое число "зажато" между ними.
Итак, начните с сортировки всех трех массивов в O (n log n). Ведение индекса в каждый массив; назовите эти i, j и k. Инициализируйте все три до нуля. Какой бы индекс ни указывал наименьшее значение, увеличьте этот индекс. То есть, если A[i] меньше, чем B[j] и C[k], приращение i; если B[j] наименьшее, приращение j; если C[k] наименьшее, приращение k. Повторяйте, отслеживая |A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]| все время. Наименьшее значение, которое вы наблюдаете во время этого марша, - ваш ответ. (Когда самая маленькая из трех находится в конце своего массива, остановитесь, потому что вы закончили.)
На каждом шаге вы добавляете один к одному индексу; но вы можете сделать это n раз для каждого массива, прежде чем наступить. Таким образом, это не более шагов 3*n, что является O (n), которое меньше O (n log n), что означает, что общее время равно O (n log n). (Или просто O (n), если вы можете предположить, что массивы отсортированы.)
Набросок доказательства того, что это работает: предположим, что A[i], B[j], C[k] являются a, b, c, которые формируют фактический ответ; то есть они имеют минимум |a-b|+|b-c|+|c-a|. Предположим далее, что a > b > c; доказательство для других случаев симметрично.
ЛЕММА: Во время нашего марша мы не увеличиваем j за прошлый j до тех пор, пока не увеличим k минус k. Доказательство. Мы всегда увеличиваем индекс наименьшего элемента и k <= K, B[J] > C[k]. Поэтому, когда j=J и k <= K, B[j] не самый маленький элемент, поэтому мы не увеличиваем j.
Теперь предположим, что мы увеличиваем k прошлое k до i доходит до i. Как все выглядит так, как только мы выполняем этот приращение? Ну, C[k] является наименьшим из трех в тот момент, потому что мы собираемся увеличивать k. A[i] меньше или равно A[i], потому что i < I и a сортируются. Наконец, j <= J, поскольку k <= K (по нашей лемме), поэтому B[j] также меньше A[i]. Взятый вместе, это означает, что наша сумма абс-дифф в этот момент меньше 2*(c-a), что является противоречием.
Таким образом, мы не увеличиваем k прошлое k до тех пор, пока i не достигнет i. Поэтому в какой-то момент во время нашего марша i=I и k=K. По нашей лемме в этой точке j меньше или равно j. Таким образом, на данный момент либо B[j] меньше, чем два других, и j будет увеличиваться; или B[j] находится между двумя другими, и наша сумма равна 2*(A[i]-C[k]), что является правильным ответом.
Это доказательство неаккуратно; в частности, он явно не учитывает случай, когда один или несколько из a, b, c равны. Но я думаю, что детали могут быть легко разработаны.
Я бы написал действительно простую программу вроде этого:
#!/usr/bin/python
import sys, os, random
A = random.sample(range(100), 10)
B = random.sample(range(100), 10)
C = random.sample(range(100), 10)
minsum = sys.maxint
for a in A:
for b in B:
for c in C:
print 'checking with a=%d b=%d c=%d' % (a, b, c)
abcsum = abs(a - b) + abs(b - c) + abs(c - a)
if abcsum < minsum:
print 'found new low sum %d with a=%d b=%d c=%d' % (abcsum, a, b, c)
minsum = abcsum
И проверяйте его снова и снова, пока я не увижу какой-то узор. Образец, который я нашел здесь, - это то, что можно было бы ожидать: числа, которые наиболее близки друг к другу в каждом наборе, независимо от того, являются ли цифры "высокими" или "низкими", являются те, которые производят наименьшую минимальную сумму. Таким образом, это становится проблемой ближайшего номера. За все это стоит, наверное, не так много.