LeetCode题解(1101):彼此熟识的最早时间(Python)
发布日期:2021-06-29 20:21:46
浏览次数:5
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月20日 03时52分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
头条号已加入爱用建站-智慧链接大家族,流量入口又增加了啦
2019-04-30
谈谈小程序的赚钱方式
2019-04-30
企业的逆袭神器——小程序
2019-04-30
干货!如何快速拥有自己的商城APP
2019-04-30
就现在而言,微信小程序还有市场吗?
2019-04-30
超级好用的智能网站小功能
2019-04-30
快来学学爱用建站新功能【Light Press】微单页,超级实用
2019-04-30
用最低的成本做到自己想要的小程序商城效果
2019-04-30
不安全!!!都2020年了,你的网站还没上HTPPS说得过去吗?
2019-04-30
没有网店经验的小商家在轻栈也可以将小程序商城搞得风生水起
2019-04-30
干货!利用微信生态推广小程序商城
2019-04-30
爱用建站智能推送一键完成全网分发,你也可以篇篇10w+
2019-04-30
微信小程序免费申请攻略
2019-04-30
内容创作新款工具“爱用博客系统”来啦
2019-04-30
免费网站制作攻略
2019-04-30
如何利用线下门店绿色通道快捷注册小程序
2019-04-30
微信小程序构建新经济圈
2019-04-30
爱用建站快速注册支付宝小程序流程
2019-04-30
爱用建站微信小程序快速上线攻略
2019-04-30
智能表单一键分发,快速收集信息
2019-04-30