首页 > 试题广场 >

集合合并

[编程题]集合合并
  • 热度指数：2536 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
给定若干个32位int数字集合，每个集合中的数字无重复，譬如：
  {1,2,3}  {2,5,6}  {8}
将其中交集不为空的集合合并，保证合并完成后所有集合之间无交集，输出合并后的集合个数以及最大集合中元素的个数。

输入描述:
输入格式：
1. 第一行为一个数字N，表示集合数。
2. 接下来N行，每行一个非空集合，包含若干个数字，数字之间用空格分开。
假设第i个集合的大小为Si，数据满足N<=100000,ΣSi<=500000


输出描述:
输出格式：
1. 第一行为合并后的集合个数。
2. 第二个为最大集合中元素的个数。
示例1

输入

3
1 2 3
2 5 6
8

输出

2
5
算法知识视频讲解
添加回答
Python
上大-黄志栋头像 上大-黄志栋
自己做的，通过率73.3%；Python编写
思路：在添加数据的时候就进行合并操作。这个想法源自插入排序，我将整个集合群作为一个列表，方便对元素操作；每个元素是个集合，这样元素（集合）之间进行并交集运算很方便。假定左边部分为没有交集的集合群，每次新添加的集合放到列表尾部，遍历其之前的各个集合，如果有交集就标记索引，遍历结束后，将索引值对应的集合与新添加的集合取并集，并把原先标记的索引处的元素弹出（因为它已经成为大并集的一部分了，自身没有存在的价值了） 
while True:
    try:
        n = int(input())
        a = []
        maxlth = 0
        for i in range(n):
            data = {int(x) for x in input().split()}
            a.append(data)
            maxlth = max(maxlth, len(data))
            j = len(a)
            b = []
            while j > 1:
                if len(a[-1] & a[j-2]) > 0:
                    b.append(j-2)
                j -= 1
            for k in b:
                a[-1] |= a[k]
                maxlth = max(maxlth, len(a[-1]))
                a.pop(k)
        print(len(a))
        print(maxlth)
    except:
        break
讨论区也有并查集算法，大家可以学习一下，我也在学习

发表于 2020-07-16 09:58:48 回复(0)
提交观点

问题信息

C++工程师 数组 小米集团 模拟 测试工程师 图 2019 Java工程师
来自：小米2019秋招软件开...
上传者：小小
难度：
1条回答 9204浏览

热门推荐

通过挑战的用户

查看代码

相关试题

集合合并

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号