K Closest Points to Origin

Средняя№973k наибольших

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

973 K Closest Points to OriginРазбор · 1×

Пример: (2, 2), (-3, 1), (1, 0), (0, -4), (-1, -2), (3, 3), k = 3. Сверху — точки, над прочитанными — d, квадрат расстояния; ниже — макс-куча по d, точка под каждым d.

2,2-3,11,00,-4-1,-23,3макс-кучаk = 3
ещё не прочитанотекущая точкав кучекорень: самая дальняя из взятыхвыброшеноответ

В куче будут 3 самые близкие точки, наверху — самая дальняя из них

01/28
сначала · назад · пуск · шаг
Скорость
1function kClosest(points, k):
2 heap = empty max-heap // ordered by d
3 for each (x, y) in points:
4 d = x * x + y * y
5 if size of heap < k:
6 push (d, x, y) into heap
7 else if d < max of heap:
8 pop max from heap
9 push (d, x, y) into heap
10 return points in heap
состояние
x
–
y
–
d
–
heap
[]
историянажмите шаг, чтобы вернуться

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

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

  1. В куче всегда k ближайших из прочитанных точек. Её корень — самая дальняя из них, поэтому новая точка попадает в кучу ровно тогда, когда она ближе корня.
  2. Это k наибольших с карточки, только наоборот: для k самых маленьких расстояний куча держит наверху самое большое — то, что уходит первым.
  3. x² + y² растёт вместе с самим расстоянием, поэтому сравнение квадратов даёт тот же порядок, и корень извлекать не нужно.

Сложность

Время O(n log k): каждая из n точек стоит не больше одного удаления и одного добавления в куче из k. Память O(k) на кучу.

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

Решить на LeetCode ↗

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