百度网上笔试题及答案

（2）处理流程：

1.将集合按照大小排序，组成集合合并待处理列表
2.选择最小的集合，找出与之有交集的集合， 如果有，合并之； 如果无，则与其它集合是独立集合，从待处理列表 中删除。
3.重复直到待处理列表为空

算法： 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索 是否有此元素存在：

1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。

2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素 都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集 合列表。转3。

3。如果待处理集合列表不为空，转2。

如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。 

算法复杂度分析：

　　假设集合的个数为n，最大的集合元素为m 排序的时间复杂度可以达到n*log(n) 然后对于元素在其他集合中查找，最坏情况下为（n-1）*m 查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。 所以最终最坏时间复杂度为O(m*m*n*n)

　　需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处 于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先 与最大的集合进行比较，这些都最大的回避了最坏情况。

(3)可能的改进：

　　首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及 合并的效率增高。 另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。

上一页  [1] [2]