集合题目

给定一个字符串的集合，格式如：
{aaa  bbb  ccc}， {bbb   ddd}，{eee   fff}，{ggg}，{ddd   hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应

输出
{aaa  bbb  ccc  ddd  hhh}，{eee   fff}， {ggg}
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度
（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

据说是百度的笔试题目，尝试着写了一下，没做过多的测试，不足之处，望请指正

package src.com.ant.test;

import java.util.ArrayList;

import java.util.HashMap;

/**

 * 集合题目

 * <p>(1)两两判断是否有交集，有则改变记录并集的集合的值，否则保存，最后将并集集合也保存

 * <p>(2)实现如下 check方法和unite方法 在最坏的情况下检测次数不会超过长度最长的集合的检测次数

 * <p>设有n个集合，最长的集合元素个数为m,则在最坏的情况下会检测m*m*(n-1)次，而合并时不会超过此最坏情况

 * <p>则整个过程下来复杂度为O(m*m*n*n)

 * <p>(3)可以在check方法和unite方法上利用其它的方法快速判断和取并集

 * @author SavageGarden

 *

 */

public class HelloWorld {



	public static int length = 0;

	public static ArrayList initList = new ArrayList();

	public static ArrayList resultList = new ArrayList();

	public static void main(String[] args){

		initList = init();

		System.out.println("合并前：initList-----------");

		for(int i = 0; i < initList.size(); i++) {

			for(int j = 0; j < ((String[])initList.get(i)).length; j++) {

				System.out.print(((String[])initList.get(i))[j]+",");

			}

			System.out.println();

		}

		resultList = mainFunc(initList);

		System.out.println("合并后：resultList---------");

		for(int i = 0; i < resultList.size(); i++){

			for(int j = 0; j < ((String[])resultList.get(i)).length; j++) {

				System.out.print(((String[])resultList.get(i))[j]+",");

			}

			System.out.println();

		}

		

	}

	/**

	 * 初始化list，得到要测试的字符串数组

	 * @author SavageGarden

	 * @return

	 */

	public static ArrayList init(){

		ArrayList list = new ArrayList();

		//初始化数组

		String[] array1 = {"aaa","bbb","ccc"};

		String[] array2 = {"bbb","ddd"};

		String[] array3 = {"eee","fff","rrr"};

		String[] array4 = {"ggg","rrr"};

		String[] array5 = {"ddd","hhh"};

		//添加到list

		list.add(array1);

		list.add(array2);

		list.add(array3);

		list.add(array4);

		list.add(array5);

		

		return list;

	}

	/**

	 * 合并两个字符串，得到其内容的并集

	 * @author SavageGarden

	 * @param a

	 * @param b

	 */

	public static String[] unite(String[] a,String[] b){

		if(a.length > 0 && b.length > 0) {

			// 首先实例化一个新的字符串数组以存储合并后的字符串数组

			//其长度为全局变量length

			String[] uniteString = new String[length];

			int status = 0;//记录uniteString的下标变化

			//如果a为长度较小的一个，则将a，b置换

			if(a.length < b.length){

				String[] c = a;

				a = b;

				b = c;

			}

			//首先将较小的字符串数组放到uniteString内

			for(int i = 0; i < b.length; i++){

				uniteString[i] = b[i];

			}

			status = b.length;//记录uniteString的下标变化

			for(int i = 0; i < a.length; i ++) {

				boolean flag = true;//标记a,b是否有相同值

				for(int j = 0; j < b.length; j++) {

					if(a[i].equals(b[j])){

						flag = false;

					}

				}

				if(flag){

					uniteString[status] = a[i];

					status ++;

				}

			}

			return uniteString;

		}

		return null;

	}

	/**

	 * 校验字符串有无交集，有则返回true,否则返回false

	 * @param a

	 * @param b

	 * @return

	 */

	public static boolean check(String[] a,String[] b){

		boolean result = false;

		if(a.length > 0 && b.length > 0) {

			int minLength = a.length < b.length?a.length:b.length;

			//只要有一个元素相同，就说明有交集，则将result置为true

			length = minLength;

			if(a.length < b.length){

				String[] c = a;

				a = b;

				b = c;

			}

			boolean flag = false;//标记a,b是否有相同值

			for(int i = 0; i < a.length; i ++) {

				for(int j = 0; j < b.length; j++) {

					if(a[i].equals(b[j])){

						result = true;

						flag = true;

					}

				}

				if(!flag){

					length ++;

				}

				flag = false;

			}

		}

		return result;

	}

	/**

	 * 判断一个要添加的字符串是否已经在数组中

	 * @param s

	 * @param list

	 * @return

	 */

	public static boolean canAdd(String[] s,ArrayList list){

		for(int i = 0; i < list.size(); i++){

			if(list.get(i).equals(s)){

				return false;

			}

		}

		return true;

	}

	/**

	 * 主方法

	 * <p>for循环判断两两之间是否有交集，有则改变uniteString的值，否则添加到resultList

	 * @param initList

	 * @return

	 */

	public static ArrayList mainFunc(ArrayList initList){

		HashMap hm = new HashMap();

		for(int i = 0; i < initList.size(); i++){

			hm.put(new Long(i), "true");

		}

		String[] uniteString = null;

		ArrayList resultList = new ArrayList();

		for(int i = 0; i < initList.size(); i++){

			if(hm.get(new Long(i)).equals("true")){

				for(int j = i+1; j< initList.size(); j++){

					if(uniteString == null){

						if(check((String[])initList.get(i),(String[])initList.get(j))){

							hm.put(new Long(i), "false");

							hm.put(new Long(j), "false");

							uniteString = unite((String[])initList.get(i),(String[])initList.get(j));

						}else{

							if(canAdd((String[])initList.get(j),resultList)){

								resultList.add((String[])initList.get(j));

							}

						}

					}else{

						if(check(uniteString,(String[])initList.get(j))){

							hm.put(new Long(i), "false");

							hm.put(new Long(j), "false");

							uniteString = unite(uniteString,(String[])initList.get(j));

						}else{

							if(canAdd((String[])initList.get(j),resultList)){

								resultList.add((String[])initList.get(j));

							}

						}

					}

				}

			}

		}

		if(uniteString == null){

			uniteString = (String[])initList.get(0);

		}

		resultList.add(uniteString);

		

		if(initList.size() == resultList.size()){

			return resultList;

		}else{

			return mainFunc(resultList);

		}

	}

 }

评论

1 楼 weixuanfeng 2010-09-30  

被你写麻烦了。这代码很好优化啊。
主要的交集是全部的交集，还是一个比下一个的交集。
你的方法结果是取所有的值且不重复。
简单就是两个方法，一个把所有的集合添加到一个总集合里面，二就是取出重复的值就可以了