※ 引述《DJYOMIYAHINA (通通打死)》之铭言:
: cnt后然后cnt多的给大的权重这样
: 比昨天简单
: 昨天好难
: ==
: def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
: cnt = [0 for _ in range(n)]
: for road in roads:
: node1, node2 = road
: cnt[node1] += 1
: cnt[node2] += 1
: cnt.sort()
: ans = 0
: for i in range(n):
: ans += (i+1)*cnt[i]
: return ans
思路:
差不多 纪录每个节点出现的次数 然后排序 最后乘起来加上去
Python Code:
class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
record = defaultdict(int)
result = 0
for road in roads:
record[road[0]] += 1
record[road[1]] += 1
sorted_value = sorted(record.values(),reverse=True)
for i in range(len(sorted_value)):
result += sorted_value[i] * n
n -= 1
return result