百度技术研发笔试题目
10-16 00:00:09
来源：http://www.qz26.com 笔试题目 阅读：8692次
导读：是否有此元素存在：1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。www.qz26.com 3。如果待处理集合列表不为空，转2。如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。算法复杂度分析：假设集合的个数为n，最大的集合元素为m排序的时间复杂度可以达到n*log(n)然后对于元素在其他集合中查找，最坏情况下为（n-1）*m查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(m*m*n*n)需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。(3)可能的改进：
百度技术研发笔试题目,标签：银行笔试题目,企业笔试题目,http://www.qz26.com
是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3
。
2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素
都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集
合列表。转3。 www.qz26.com
3。如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m
排序的时间复杂度可以达到n*log(n)
然后对于元素在其他集合中查找，最坏情况下为（n-1）*m
查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)
合并的时间复杂度不会超过查找集合有交集的最坏情况。
所以最终最坏时间复杂度为O(m*m*n*n)
需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处
于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先
与最大的集合进行比较，这些都最大的回避了最坏情况。
(3)可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及
合并的效率增高。
另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3
。
2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素
都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集
合列表。转3。 www.qz26.com
3。如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m
排序的时间复杂度可以达到n*log(n)
然后对于元素在其他集合中查找，最坏情况下为（n-1）*m
查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)
合并的时间复杂度不会超过查找集合有交集的最坏情况。
所以最终最坏时间复杂度为O(m*m*n*n)
需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处
于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先
与最大的集合进行比较，这些都最大的回避了最坏情况。
(3)可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及
合并的效率增高。
另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
Tag:笔试题目，银行笔试题目,企业笔试题目，求职笔试面试 - 笔试题目
下一条：2016兴业银行长沙笔试题