• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1101.彼此熟识的最早时间|TheEarliestMomentWhenEveryoneBecomeFriend ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

In a social group, there are N people, with unique integer ids from 0 to N-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends.  Friendship is symmetric: if A is friends with B, then B is friends with A.

Let's say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

Example 1:

Input: logs = 6
Output: 20190301
Explanation: 
The first event occurs at timestamp = 20190101 and after 0 and 1 become friends we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104 and after 3 and 4 become friends we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107 and after 2 and 3 become friends we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211 and after 1 and 5 become friends we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224 and as 2 and 4 are already friend anything happens.
The sixth event occurs at timestamp = 20190301 and after 0 and 3 become friends we have that all become friends.

Note:

  1. 1 <= N <= 100
  2. 1 <= logs.length <= 10^4
  3. 0 <= logs[i][0] <= 10^9
  4. 0 <= logs[i][1], logs[i][2] <= N - 1
  5. It's guaranteed that all timestamps in logs[i][0] are different.
  6. Logs are not necessarily ordered by some criteria.
  7. logs[i][1] != logs[i][2]

在一个社交圈子当中,有 N 个人。每个人都有一个从 0 到 N-1 唯一的 id 编号。

我们有一份日志列表 logs,其中每条记录都包含一个非负整数的时间戳,以及分属两个人的不同 id,logs[i] = [timestamp, id_A, id_B]

每条日志标识出两个人成为好友的时间,友谊是相互的:如果 A 和 B 是好友,那么 B 和 A 也是好友。

如果 A 是 B 的好友,或者 A 是 B 的好友的好友,那么就可以认为 A 也与 B 熟识。

返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间,就返回 -1 。

示例:

输入:logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出:20190301
解释:
第一次结交发生在 timestamp = 20190101,0 和 1 成为好友,社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104,3 和 4 成为好友,社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107,2 和 3 成为好友,社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211,1 和 5 成为好友,社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224,2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301,0 和 3 成为好友,大家都互相熟识了。

提示:

  1. 1 <= N <= 100
  2. 1 <= logs.length <= 10^4
  3. 0 <= logs[i][0] <= 10^9
  4. 0 <= logs[i][1], logs[i][2] <= N - 1
  5. 保证 logs[i][0] 中的所有时间戳都不同
  6. Logs 不一定按某一标准排序
  7. logs[i][1] != logs[i][2]

 368ms

 1 class Solution {
 2     func earliestAcq(_ logs: [[Int]], _ N: Int) -> Int {
 3         var logs = logs
 4         logs.sort(by:{return $0[0] < $1[0]})
 5         let dsu:DisjointSetUnion = DisjointSetUnion(N)
 6         for i in logs
 7         {
 8             dsu.AddEdge(i[1] + 1, i[2] + 1)
 9             if dsu.GetSize(1) == N
10             {
11                 return i[0]
12             }
13         }
14         return -1
15     }
16 }
17 
18 class DisjointSetUnion
19 {
20     var N_:Int
21     var par_:[Int]
22     var size_:[Int]
23     
24     init(_ N:Int)
25     {
26         self.N_ = N
27         self.par_ = [Int](repeating:0,count:N_ + 1)
28         self.size_ = [Int](repeating:1,count:N_ + 1)
29         for i in 0..<N
30         {
31             par_[i] = i
32         }
33     }
34     
35     // Returns the parent of |x|'s set.
36     func GetParent(_ x:Int) -> Int
37     {
38         if par_[x] != x
39         {
40             par_[x] = GetParent(par_[x])
41         }
42         return par_[x]
43     }
44     
45     // Returns the size of set in which |x| belongs.
46     func GetSize(_ x:Int) -> Int
47     {
48         return size_[GetParent(x)]
49     }
50     
51     // Add an edge between |u| and |v|. Creates union of both sets.
52     func AddEdge(_ u:Int,_ v:Int)
53     {
54         var parent_u:Int = GetParent(u)
55         var parent_v:Int = GetParent(v)
56         if parent_u != parent_v
57         {
58             if size_[parent_v] > size_[parent_u]
59             {
60                 let temp:Int = parent_u
61                 parent_u = parent_v
62                 parent_v = temp
63             }
64             par_[parent_v] = parent_u
65             size_[parent_u] += size_[parent_v]
66             size_[parent_v] = 0
67         }
68     }
69 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift按钮UIbutton里的图片位置居右/居左发布时间:2022-07-13
下一篇:
[学习笔记]菜鸟教程Swift知识点总结(一)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap