Max Points on a Line

Сложная№149подсчёт

Даны точки на плоскости, все разные. Нужно найти, сколько больше всего из них лежит на одной прямой. Наш пример: (1, 1), (2, 3), (4, 2), (3, 5), (0, 4), (5, 9) — ответ 4: (1, 1), (2, 3), (3, 5) и (5, 9) лежат на одной прямой.

149 Max Points on a LineРазбор · 1×

Пример: точки (1, 1), (2, 3), (4, 2), (3, 5), (0, 4), (5, 9). Каждая точка по очереди становится p; словарь считает точки после неё по наклону прямой от p. Пунктир — лучшая прямая на этот момент.

01234501234567891,12,34,23,50,45,9countнаклон: точек—
точка pq или самый частый наклонуже в паре с pуже была pлучшая прямая

Одна точка всегда лежит на прямой: best = 1

01/56
сначала · назад · пуск · шаг
Скорость
1function maxPoints(points):
2 best = 1
3 for each p in points:
4 count = empty map // slope: points
5 for each q after p in points:
6 count[slope(p, q)] += 1
7 top = largest value in count, or 0
8 best = max(best, top + 1)
9 return best
состояние
p
–
q
–
count
–
top
–
best
1
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Две прямые через одну точку p с одинаковым наклоном — это одна прямая. Значит, точки после p с общим наклоном лежат на одной прямой с p, и словарь их считает.
  2. Наклон храним сокращённой дробью dy/dx, а не результатом деления: 4/2 и 2/1 дают один ключ, нет ошибок округления, а вертикальная прямая — просто 1/0.
  3. Прямая через более раннюю точку уже посчитана, когда та была p, поэтому каждая p смотрит только на точки после себя.

Сложность

Время O(n²): каждую пару точек смотрим один раз (сокращение дроби добавляет короткий НОД). Память O(n): в словаре не больше n − 1 наклонов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.