給定一個字符串的集合，格式如：
{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空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
