Ответ 1
Прохладная вещь о расстоянии Манхатана заключается в том, что само расстояние состоит из двух независимых компонентов: расстояния по координатам x и y. Таким образом, вы можете решить две более простые задачи и объединить полученные результаты для получения желаемых результатов.
Задача, о которой я говорю, такова: заданы точки на линии. Найдите точку на линии, которая минимизирует сумму абсолютных расстояний до всех точек. Если их найти много (кстати, они всегда превращаются в один сегмент, который легко доказать). Сегмент определяется (потенциально двумя) точками медианы множества. Посредством я имею в виду точку, которая имеет равное количество точек слева и справа от нее. В случае, если число точек нечетное, такой точки нет, и вы выбираете точки с разностью 1 в обоих направлениях для формирования сегмента.
Здесь я добавляю примеры решений этой более простой задачи:
В случае, если точки на линии выглядят так:
-4 | | | 0 | 2 3 4
^
Решение - это просто точка и 2.
В случае, если точки на линии выглядят так:
-4 | | | 0 | 2 3
^---^
Весь отрезок [0, 2] является решением задачи.
Вы решаете эту задачу отдельно для координат x и y, а затем объединяете результаты, чтобы получить прямоугольник минимальных дистанционных точек.
ПРИМЕР
И вот теперь пример решения для начальной задачи.
Представьте, что вы хотите найти точки с минимальным расстоянием Манхатана до набора (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)
Вы создаете две более простые задачи:
Для x:
0 1 2 3 3 4
^-^
И здесь решение - это сегмент [2, 3] (обратите внимание, что здесь мы дублируем точку 3, которую я представлял, возможно, не самым интуитивным образом).
Для y:
3 3 4 5 6 7
^-^
Здесь решение является отрезком [4, 5].
Наконец, мы получим, что решение начальной задачи - это прямоугольник с формулой:
2 <= x <= 3; 4 <= y <= 5
КОМПЛЕКСНОСТЬ
Как многие люди проявляют интерес к этому сообщению, я решил улучшить его немного больше.
Расскажите о сложности.
Сложность задачи на самом деле такая же, как сложность решения более простой задачи (поскольку, как уже говорилось, решение фактически состоит из решения двух более простых задач). Многие люди пойдут и решают его, сортируя, а затем выбирая медиан. Однако это вызовет сложность O(nlog n), где n - количество точек в наборе входных данных.
Это может быть улучшено, если используется лучший алгоритм для нахождения k-го элемента (Пример реализации в С++ STL). Этот алгоритм в основном следует тому же подходу, что и qsort. Время работы O(n). Даже в случае двух медианных точек это будет оставаться линейным (требуется два прогона одного и того же алгоритма), и, таким образом, общая сложность алгоритма становится O(n). Очевидно, что задача не может быть решена быстрее, если сам вход имеет указанную сложность.