脸家店面

say543 发表于 2017-10-17 14:53
我只想到 brute force 解 .... 只有同个set elements in order 的条件吗?

想到brute force也很好，然后再优化嘛
set內元素是无序的

求问楼主union find如何做的！谢谢！！

第2题很简单啊： 建一个Map： element -> set 。 每次traverse 这个set 里面所有的元素， 如果在Map 里面已经存在的话， 就Update Map

第二个题目，也可以建一个图
点是每个set，两个set有交集就连一条边

然后，用BFS或者DFS走一遍，把连通的几个set合并
若n是set的个数，每个set平均m个元素
1）建图时间复杂度 n^2 * m
2) 判断连通 O(n + e)  , e是边的数目

建图的时间复杂度

求问LZ第二题Union find怎么做呀？谢谢 LZ

第一个题是binary tree么，如果是一般树的话 岂不是很难

haifengc 发表于 2017-10-18 02:35
第二个题目，也可以建一个图
点是每个set，两个set有交集就连一条边

这太复杂了，on就能解决的

一个map来记录元素的parent，union-find遍历所有元素并更新，最后根据cluster输出元素就行了。

楼主，想问下这个电面是会现场在电脑上run代码么？还是单纯的让口头run呢？
谢谢！！

clould365 发表于 2017-10-18 13:22
第一个题是binary tree么，如果是一般树的话 岂不是很难

这是个好问题！给的是binary tree。