Привет, гении и не очень!
Сегодня, мы с вами перенесемся в мир двумерных координат! 🎮 А если точнее, будем соединять точки на плоскости так, чтобы не превратить всё в хаос. Поехали!
Что нас ждёт в этой забавной задачке 🎉
Итак, сегодня нашей задачей будет соединить какие-то точки на двумерной плоскости с минимальными затратами. Что это, конкурс на самую экономную сеть метро? Почти! 🚇
В чём прикол, ребята 🎭
Дадим вам набор точек на координатной плоскости. А вам нужно их соединить, не превратив всё в микс из "Симпсонов" и хентая. Что? Ну как бы да, манхэттенское расстояние и всё такое.
👉 Оригинальная задача, если интересно
Начнем с начала: поймем, что у нас есть 🦉
Вы когда-нибудь пробовали соединять звезды на небе, превращая их в созвездия? Нет? А зря! По сути, наша задача не сильно отличается.
# Все наши "звезды" и их "созвездия"
edges = []
for i in range(len(points)):
for j in range(i+1, len(points)):
cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((cost, i, j))
Теперь сортируем их, как комиксы на полке 📚
Кто из вас сортирует комиксы по алфавиту? Никто? ОК, неважно. Давайте сортируем наши "звезды" по расстоянию между ними.
# Сортировка по расстоянию, как в настоящей космической одиссее
edges.sort()
Подключаем точки, не забывая про теорию хаоса 🌪️
Подключаем точки, как в том фильме "Соединение". Только без мистики и с меньшим бюджетом.
# Кто твой папа, точка?
parent = list(range(len(points)))
def find(u):
if u != parent[u]:
parent[u] = find(parent[u])
return parent[u]
# Собираем всё в одно большое и счастливое созвездие
mst_weight = 0
for cost, u, v in edges:
u = find(u)
v = find(v)
if u != v:
mst_weight += cost
parent[v] = u
Итак, что у нас получилось? 🎬
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
# Да, это все те же "звезды" и "созвездия"
edges = []
for i in range(len(points)):
for j in range(i+1, len(points)):
cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((cost, i, j))
# Сортируем, как настоящие космонавты
edges.sort()
# Ищем папу для каждой точки
parent = list(range(len(points)))
def find(u):
if u != parent[u]:
parent[u] = find(parent[u])
return parent[u]
# Собираем наше созвездие
mst_weight = 0
for cost, u, v in edges:
u = find(u)
v = find(v)
if u != v:
mst_weight += cost
parent[v] = u
return mst_weight
Асимптотика 🤓
Ой, чуть не забыл! Асимптотика, это как рейтинг шуток в стендапе: всегда нужно знать, какова их "скорость". В нашем случае, мы работаем с алгоритмом, который имеет временную сложность O(n^2*logn). Почему?
- O(n^2) для перебора всех возможных "соединений" между точками.
- O(logn)O(logn) для сортировки и нахождения "папы" для каждой точки (да-да, так устроена наша вселенная).
Всё это делается для n точек, так что держите это в уме, когда будете соединять свои точки, как в последнем трендовом челлендже TikTok. 😂
Заключение 🥳
Ну вот и всё, друзья! Сегодня мы научились не только соединять точки, но и делать это с минимальными затратами! В следующий раз расскажу, как сделать это с максимальными затратами, потому что... почему бы и нет? 🤷♂️
P.S. Анекдот для завершения: Почему программисты так не любят природу? Потому что там слишком много багов! 🐞🦋😂
Доп. материалы 📚
Чао! 👋