求解！ITAT大赛Java试题答案

Question

编写一个Java应用程序，对于给定的一个字符串的集合，格式如：
　　{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
　　要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出：
　　{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
　　
　　（1）分析问题，描述你解决这个问题的思路、处理流程，以及算法复杂度。
　　（2）编程实现题目要求的集合合并。
　　（3）描述可能的改进（改进的方向如效果，算法复杂度，性能等等）。请大家帮帮忙！！！

Answer 1

package util;import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;public class Test {
//循环比对，有重复的，重新放进一个set，把set放进list，然后重新遍历
public static List<Set<String>> test(List<Set<String>> list) {
if (list != null && list.size() > 0) {
for (int i = 0; i < list.size(); i++) {
Set<String> compareSet = list.get(i);
for (int j = i + 1; j < list.size(); j++) {
Set<String> set = list.get(j);
if (!compareSet(compareSet, set)) {
Set<String> newSet = heBingSet(compareSet, set);
list.remove(j);
list.remove(i);
list.add(newSet);
i=-1;
break;
}
}
}
}
return list;
} // 判断2个set有没有重复
public static boolean compareSet(Set<String> set1, Set<String> set2) {
boolean result = false;
int set1Size = set1.size();
int set2Size = set2.size();
Set<String> newSet = heBingSet(set1, set2);
int newSetSize = newSet.size();
// 没有重复
if (newSetSize == set1Size + set2Size) {
result = true;
} else {
result = false;
}
return result;
} // 合并2个set集合
public static Set<String> heBingSet(Set<String> set1, Set<String> set2) {
Iterator<String> it1 = set1.iterator();
Iterator<String> it2 = set2.iterator();
Set<String> newSet = new HashSet<String>();
while (it1.hasNext()) {
String str = it1.next();
newSet.add(str);
}
while(it2.hasNext()){
String str = it2.next();
newSet.add(str);
}
return newSet;
} public static void main(String[] args) {
// 构建题目的数据，5个set集合，并将所有集合放入一个list中
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
Set<String> set3 = new HashSet<String>();
Set<String> set4 = new HashSet<String>();
Set<String> set5 = new HashSet<String>();

set1.add("aaa");
set1.add("bbb");
set1.add("ccc"); set2.add("bbb");
set2.add("ddd"); set3.add("eee");
set3.add("fff"); set4.add("ggg"); set5.add("ddd");
set5.add("hhh"); List<Set<String>> list = new ArrayList<Set<String>>();

list.add(set1);
list.add(set2);
list.add(set3);
list.add(set4);
list.add(set5); List<Set<String>> result = test(list);
for (Set<String> set : result) {
for (String str : set) {
System.out.print(str + ",");
}
System.out.println();
}
}}

Answer 2

思路就是用set集合，来确定是否有重复的，递归来解决
不过我程序时循环，因为我让i=-1重新遍历了，改进嘛，我觉得效率上不高，但是没经过测试
复杂度应该不高吧

Answer 3

吧数据放到set中，然后把第一个集合作为原始集合，然后用后面的集合中的元素挨个和这个集合中的元素进行比较，如果有相同的，就把不同的元素合并到原始集合中，然后删除这个集合这样可以有效的避免重复比较，跟#7楼的看法 一致

Answer 4

不太明白，如果集合是这样的：  {aaa, bbb, ccc}  {eee, fff}, {aaa, fff}
第二个和第一个比较，不合并
第三个和第一个比较，把"fff"合并进去，并删除第三个集合
这时第一个和第二个集合就有交集了啊，不重复比较，怎么解决这种情况？？

Answer 5

10楼是对的，算法应该是这样的：
假设原始的originalList : {aaa, bbb, ccc}  {eee, fff}, {aaa, fff} ......
新建一个resultList:{aaa,bbb,ccc},并把 {aaa, bbb, ccc}从originalList是删除。
while(oiginalList.size()!=0){
    从resultList中找出所有与originalList.get(0)有交集的集合
     把这些集合与orginalList.get(0)合并
     把合并的结果放入resultList中
     从resultList中删除那些有交集的集合。
     把originalList.get(0)从originalList中删除。
}

Answer 6

package interview;import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;public class UnionSet { /**
 * @param args
 * 问题描述：编写一个Java应用程序，对于给定的一个字符串的集合，格式如： 
 * {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh} 
 * 要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出： 
 * {aaa bbb ccc ddd hhh}，{eee fff}， {ggg} 
 *（1）分析问题，描述你解决这个问题的思路、处理流程，以及算法复杂度。 
 *（2）编程实现题目要求的集合合并。 
 *（3）描述可能的改进（改进的方向如效果，算法复杂度，性能等等）。 
 *
 */
static List<Set<String>> method1(List<Set<String>> origiList){
List<Set<String>> result = new LinkedList<Set<String>>();

while(origiList.size() != 0){
List<Set<String>> temp = new LinkedList<Set<String>>();
Set<String> first = origiList.get(0);
origiList.remove(first);
boolean flag = true;
while(flag){
flag = false;

for(Set<String> set : origiList){
for(String str : set){
if(first.contains(str)){
first.addAll(set);
temp.add(set);
flag = true;

}
}
}
for(Set<String> s:temp){
origiList.remove(s);
}

}

result.add(first);

}


return result;



}
public static void main(String[] args) {
// TODO Auto-generated method stub
      List<Set<String>> origiList = new LinkedList<Set<String>>();
      Set<String> s1 = new HashSet<String>();
      s1.add("aaa");
      s1.add("bbb");
      s1.add("ccc");
      Set<String> s2 = new HashSet<String>();
      s2.add("bbb");
      s2.add("ddd");
      Set<String> s3 = new HashSet<String>();
      s3.add("eee");
      s3.add("fff");
      Set<String> s4 = new HashSet<String>();
      s4.add("ggg");
      Set<String> s5 = new HashSet<String>();
      s5.add("hhh");
      s5.add("ddd");
      origiList.add(s1);
      origiList.add(s2);
      origiList.add(s3);
      origiList.add(s4);
      origiList.add(s5);
      for(Set<String> s: origiList){
       for(String str: s){
       System.out.print(str+" ");
       }
       System.out.println("\n");
      }
    
      System.out.println("--------------------------->");
      origiList = method1(origiList);
      for(Set<String> s: origiList){
       for(String str: s){
       System.out.print(str+" ");
       }
       System.out.println("\n");
      }
      
}}
运行结果：
aaa ccc bbb ddd bbb fff eee ggg hhh ddd --------------------------->
hhh aaa ddd ccc bbb fff eee ggg 

Answer 7

你们编码怎么都一个一个add啊.
ArrayList<HashSet<String>> originalList=new ArrayList<HashSet<<String>>();
originalList.addAll(
new HashSet<String>.addAll("aaa", "bbb", "ccc"),
new HashSet<String>.addAll("bbb", "bbb"),
new HashSet<String>.addAll("eee", "fff"),
new HashSet<String>.addAll("ggg"),
new HashSet<String>.addAll("ddd", "hhh")
);