- 851.喧闹和富有
- 暴力BFS超时
- DFS
- 拓扑排序
class Solution(object):
def loudAndRich(self, richer, quiet):
# DAG
edges = defaultdict(list)
for r in richer:
edges[r[1]].append(r[0])
num = len(quiet)
ans = [0] * num
for i in range(num):
if i not in edges:
ans[i] = i
else:
# BFS
q = deque(edges[i])
mn, node = quiet[i], i
while q:
cur = q.popleft()
if cur in edges:
for temp in edges[cur]:
q.append(temp)
if quiet[cur] < mn:
mn = quiet[cur]
node = cur
ans[i] = node
return ans
时间复杂度： O ( m n ) O(mn) O(mn)，往上走
DFS
-
建DAG，同样的没钱指向有钱
-
DFS，邻居们的钱我不全拿，我只拿最少的。
-
注意，不要重复S
class Solution(object):
def loudAndRich(self, richer, quiet):
# DAG
edges = defaultdict(list)
for r in richer:
edges[r[1]].append(r[0])
n = len(quiet)
ans = [-1] * n
# DFS
def dfs(x):
# base
if ans[x] != -1:
return
ans[x] = x
for y in edges[x]:
dfs(y)
if quiet[ans[x]] > quiet[ans[y]]:
ans[x] = ans[y]
for i in range(n):
dfs(i)
return ans
执行用时：56 ms, 在所有 Python 提交中击败了66.67%的用户
内存消耗：19.9 MB, 在所有 Python 提交中击败了66.67%的用户
时间复杂度：
O
(
m
+
n
)
O(m+n)
O(m+n)
空间复杂度：
O
(
m
+
n
)
O(m+n)
O(m+n)
拓扑排序
- 什么是拓扑排序？Bilibili，你就知道。
- 还是建DAG，这次是有钱指向没钱
- 拓扑排序，和BFS相似
class Solution(object):
def loudAndRich(self, richer, quiet):
num = len(quiet)
# DAG rich ——> poor
edges = defaultdict(list)
inDegree = [0] * num
for r in richer:
edges[r[0]].append(r[1])
inDegree[r[1]] += 1
ans = [i for i in range(num)]
# Topological Sorting
q = deque([i for i in range(num) if inDegree[i] == 0])
while q:
x = q.popleft()
for y in edges[x]:
if quiet[ans[y]] > quiet[ans[x]]:
ans[y] = ans[x]
inDegree[y] -= 1
if inDegree[y] == 0:
q.append(y)
return ans
执行用时：68 ms, 在所有 Python 提交中击败了11.11%的用户
内存消耗：20.1 MB, 在所有 Python 提交中击败了33.33%的用户
时间复杂度：
O
(
m
+
n
)
O(m+n)
O(m+n)，没有重复计算
空间复杂度：
O
(
m
+
n
)
O(m+n)
O(m+n)，点和边
