1、問題描述

將多個集合合并成沒有交集的集合。
給定一個字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的復雜度
（3）請描述可能的改進。

2、分析

1. 假定每個集合編號為0，1，2，3...
??? 2. 創建一個hash_map，key為字符串，value為一個鏈表，鏈表節點為字符串所在集合的編號。遍歷所有的集合，將字符串和對應的集合編號插入到hash_map中去。
??? 3. 創建一個長度等于集合個數的int數組，表示集合間的合并關系。例如，下標為5的元素值為3，表示將下標為5的集合合并到下標為3的集合中去。開始時將所有值都初始化為-1，表示集合間沒有互相合并。在集合合并的過程中，我們將所有的字符串都合并到編號較小的集合中去。
??? 遍歷第二步中生成的hash_map，對于每個value中的鏈表，首先找到最小的集合編號（有些集合已經被合并過，需要順著合并關系數組找到合并后的集合編號），然后將鏈表中所有編號的集合都合并到編號最小的集合中（通過更改合并關系數組）。
??? 4.現在合并關系數組中值為-1的集合即為最終的集合，它的元素來源于所有直接或間接指向它的集合。
??? 0: {aaa bbb ccc}
??? 1: {bbb ddd}
??? 2: {eee fff}
??? 3: {ggg}
??? 4: {ddd hhh}
??? 生成的hash_map，和處理完每個值后的合并關系數組分別為
??? aaa: 0???????????
??? bbb: 0, 1????????
??? ccc: 0??????????
??? ddd: 1, 4???????
??? eee: 2???????????
??? fff: 2??????????
??? ggg: 3???????????
??? hhh: 4??????????
??? 所以合并完后有三個集合，第0，1，4個集合合并到了一起，
??? 第2，3個集合沒有進行合并。

3、具體實現

1: class DisjointSetProblem { 2: private final int SIZE = 7; 3: private int[] father; 4: private static List<Set<String>> resultList = new ArrayList<Set<String>>(); 5:? 6: public static void main(String[] args) { 7: String[] str0 = { "aaa", "bbb", "ccc", }; 8: String[] str1 = { "bbb", "ddd", }; 9: String[] str2 = { "eee", "fff", }; 10: String[] str3 = { "ggg", }; 11: String[] str4 = { "ddd", "hhh", }; 12: String[] str5 = { "xx", "yy", }; 13: String[] str6 = { "zz", "yy", }; 14: String[][] strs = { str0, str1, str2, str3, str4, str5, str6 }; 15: //change String[][] to List<Set> 16: for (String[] str : strs) { 17: //when I write--"Arraylist list=Arrays.asList(strArray)","addAll()" is unsupported for such a arraylist. 18: Set<String> set = new HashSet<String>(); 19: set.addAll(Arrays.asList(str)); 20: resultList.add(set); 21: } 22: DisjointSetProblem disjointSet = new DisjointSetProblem(); 23: disjointSet.disjoin(strs); 24: } 25:? 26: /* 27: * 獲取hashmap過程 28: * */ 29: public void disjoin(String[][] strings) { 30: if (strings == null || strings.length < 2) 31: return; 32: initial(); 33: // 獲得hash_map：key為字符串，value為一個鏈表 34: Map<String, List<Integer>> map = storeInHashMap(strings); 35: // 并查集進行合并 36: union(map); 37: } 38:? 39: //in the beginning,each element is in its own "group". 40: public void initial() { 41: father = new int[SIZE]; 42: for (int i = 0; i < SIZE; i++) { 43: father[i] = i; 44: } 45: } 46:? 47: /* Map<k,v> 48: * key:String 49: * value:List<Integer>-in which sets the string shows up. 50: */ 51: public Map<String, List<Integer>> storeInHashMap(String[][] strings) { 52: Map<String, List<Integer>> map = new HashMap<String, List<Integer>>(); 53: for (int i = 0; i < SIZE; i++) { 54: for (String each : strings[i]) { 55: if (!map.containsKey(each)) { 56: List<Integer> list = new ArrayList<Integer>(); 57: list.add(i); 58: map.put(each, list); 59: } else { 60: map.get(each).add(i); 61: } 62: } 63: } 64:? 65: // 打印出map 66: System.out.println("集合映射所生成的hashmap為："); 67: printMap(map); 68: return map; 69: } 70:? 71: private void printMap(Map<String, List<Integer>> map) { 72: // TODO Auto-generated method stub 73: Iterator<Map.Entry<String, List<Integer>>> iter = map.entrySet() 74: .iterator(); 75: while (iter.hasNext()) { 76: Map.Entry<String, List<Integer>> entry = iter.next(); 77: String key = entry.getKey(); 78: List<Integer> value = entry.getValue(); 79: System.out.println(key + ":" + value); 80: } 81: System.out.println(); 82: } 83:? 84: /* 85: * 對hashmap進行并查集合并操作 86: * */ 87: public void union(Map<String, List<Integer>> map) { 88: Iterator<Map.Entry<String, List<Integer>>> it = map.entrySet() 89: .iterator(); 90: while (it.hasNext()) { 91: Map.Entry<String, List<Integer>> entry = it.next(); 92: List<Integer> value = entry.getValue(); 93: unionHelp(value);//the arrays whose indexes are in the same list should be merged to one set. 94: } 95: // 打印出father父節點信息 96: System.out.println("hashmap集合合并之后的父節點信息為："); 97: printFather(father);//System.out.println("the father array is " + Arrays.toString(father)); 98: printSetList(resultList); 99: //merge two sets 100: for (int i = 0; i < SIZE; i++) { 101: if (i != father[i]) { 102: // set：無重復元素 103: Set<String> dest = resultList.get(father[i]); 104: Set<String> source = resultList.get(i); 105: dest.addAll(source); 106: } 107: } 108: //clear a set which has been added. 109: // 當B集合添加到A集合后，清空B集合 110: for (int i = 0; i < SIZE; i++) { 111: if (i != father[i]) { 112: resultList.get(i).clear(); 113: } 114: } 115: System.out.println("合并后:" + resultList); 116: } 117:? 118: public void unionHelp(List<Integer> list) { 119: int minFather = getFather(list.get(0));//list[0] is the smaller. 120: // 傳過來的list參數已經排好序 121: for (int i = 0, size = list.size(); i < size; i++) { 122: //father[list.get(i)] = minFather; 123: unionHelp(list.get(0),list.get(i)); 124: } 125: } 126:? 127: // 路徑壓縮 128: public int getFather(int x) { 129: while (x != father[x]) { 130: x = father[x]; 131: } 132: return x; 133: } 134:? 135: private void printFather(int[] fatherNode) { 136: // TODO Auto-generated method stub 137: for (int node : fatherNode) 138: System.out.print(node + " "); 139: System.out.println(); 140: } 141:? 142: private void printSetList(List<Set<String>> list) { 143: // TODO Auto-generated method stub 144: System.out.print("合并前:"); 145: for (int i = 0; i < SIZE; i++) { 146: System.out.print(list.get(i) + " "); 147: } 148: System.out.println(); 149: } 150:? 151: //general union in disjoin set.But we overload it in this case. 152: public void unionHelp(int x, int y) { 153: if (father[x] != father[y]) { 154: int fx = getFather(x); 155: int fy = getFather(y); 156: //merge two arrays to the array that has a smaller index. 157: if (fx < fy) { 158: father[y] = fx; 159: } else { 160: father[x] = fy; 161: } 162: } 163: } 164: 165: }

轉載于:https://www.cnblogs.com/ttltry-air/archive/2012/08/14/2638437.html

總結

以上是生活随笔為你收集整理的多个集合合并成没有交集的集合-实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。