LeetCode题解(1101):彼此熟识的最早时间(Python)
发布日期:2021-06-29 20:21:46
浏览次数:4
分类:技术文章
本文共 1526 字,大约阅读时间需要 5 分钟。
题目:(中等)
标签:并查集、排序
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( N ) O(N) O(N) | O ( N ) O(N) O(N) | 48ms (100.00%) |
Ans 2 (Python) | |||
Ans 3 (Python) |
解法一:
class DSU: def __init__(self, n: int): self._n = n self._array = [i for i in range(n)] self._size = [1] * n self._group_num = n def find(self, i: int) -> int: """查询i所在的连通分支:O(1)""" if self._array[i] != i: self._array[i] = self.find(self._array[i]) return self._array[i] def union(self, i: int, j: int) -> bool: """合并i和j所属的连通分支:O(1)""" i, j = self.find(i), self.find(j) if i != j: self._group_num -= 1 if self._size[i] >= self._size[j]: self._array[j] = i self._size[i] += self._size[j] else: self._array[i] = j self._size[j] += self._size[i] return True else: return False def is_connected(self, i: int, j: int) -> bool: return self.find(i) == self.find(j) @property def group_num(self): """计算连通分支数量:O(1)""" return self._group_num @property def max_group_size(self): """计算最大连通分支包含的数量:O(N)""" import collections return max(collections.Counter(self._array).values())class Solution: def earliestAcq(self, logs: List[List[int]], n: int) -> int: logs.sort() dsu = DSU(n) for date, a, b in logs: dsu.union(a, b) if dsu.group_num == 1: return date return -1
转载地址:https://dataartist.blog.csdn.net/article/details/117185561 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月18日 17时34分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
OAuth授权看这篇就够了
2019-04-30
Open API
2019-04-30
CSM(Certified Scrum Master) 敏捷认证是什么?
2019-04-30
软件开发流程
2019-04-30
面向工资编程,每年加薪 30% 的秘诀
2019-04-30
使用JavaScript和React编写原生移动应用
2019-04-30
什么是架构、框架、模式和平台
2019-04-30
.Net面试题一
2019-04-30
NPOI导出excel
2019-04-30
Newtonsoft.Json
2019-04-30
JsonHelper
2019-04-30
KeyValuePair<string, string>
2019-04-30
NameValuePair 简单名称值对节点类型
2019-04-30
DataTime.Now.Ticks
2019-04-30
private、protected、public和internal的区别
2019-04-30
签名和验签
2019-04-30
JArray
2019-04-30
China Union Pay helper
2019-04-30
C#向远程地址发送数据
2019-04-30
C#签名验签帮助类
2019-04-30