给定一个字符串的集合，格式如：
{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应
输出
{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度
（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。
====================================================================
【原创】分析：题意很明显不分析了。借鉴我处理文本分类的经验，给出我的思路，
建立一个倒排索引，所谓的倒排索引，就是以关键词为key，value中保存包含该
关键词的文档标号，这种方法普遍应用在搜索、信息检索领域。于是就上面的例子，建立
倒排索引如下：
-------------------
key value
------------------
aaa 1
bbb 1,2
ccc 1
ddd 2,5
eee 3
fff 3
ggg 4
hhh 5
----------------------
建立倒排索引的时间复杂度为O(N);然后根据value，求交集（判断交集的方法，见我的另一篇日志），具体操作是往上合并，例如
{1}+{1，2}={1，2}；...,{1,2}+{2,5}={1，2，5}；这样前四个合并了，接下来的三个，无法与{1，2，5}合并，形成3个集合
{1，2，5} {3} {4}，最后的{5}往回比较，最后确认是与{1，2，5}合并，，如此往复，知道遍历所有元素。根据集合中的文档编号，将
对应位置的集合合并即可。
注意的地方：可以只处理value中元素个数大于1的数，其它value只有1个元素的，要么是单独的集合，要么已经被包含了，如3，4都不用考虑，而5已经被{2，5}包含，所有这样会减少很多操作步骤，大大降低时间复杂度，
此算法最好的时间复杂度是各集合都没有交集，即value中元素个数是1，那么建立索引后就不用合并，总的时间复杂度为O(N)=建立倒排索引的时间复杂度;
最坏的情况发生在每个集合都只与另外一个（有且只有一个）集合有交集。这样，整个集合空间被划分为logN个（以2为底）。这样判断交集的次数的时间复杂度为O（logN*logN)=[1+2+3+...+logN],所以总的时间复杂度为O(N)+O(logN*logN)=O(N);
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
