给定一个字符串的集合,格式如:
{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);
}
}
}
分享到:
相关推荐
基础算法题目精简集合 题目相对来说简要了一些,算是有代表性了,各方面都有题目 偶不希望像别的帖子那样像为了凑数般弄够100题,相反这里不过二三十。 前六章均为算法基础入门必会解答的题目,也就是若当中有任何一...
非常适合初学python者,学习后用来巩固基础的练习题
高一数学集合习题及答案.pdf
ArrayList方法介绍及源码分析其实就是一句话,List集合是有序的,根据索引(index)来访问元素,另外,list集合允许有重复的元素 ArrayList是List的实现
一些比较基础的java面试题,包含多线程,集合,框架,网络相关的知识点。
答题小程序 list 题目集合
经典算法设计与分析编程题集合划分题目和代码实现
详细而又全面的Java编程题集合。 共76道题目。
里面包含了c和java的一下算法题目和答案。希望能帮助到大家
分别采用数组与链表,“求两个集合的合并运算”与“两个有序表合并后仍然有序”,要求编程实现。 题目一 求两个集合的合并运算 题目二 求两个有序表合并算法
JAVA笔试题集合, 面试常用的JAVA题目, 找工作必看。
武汉C#面试题目集合准备了好久才集合起来的 希望对朋友们有用途。
727_基础题目集合,727_基础题目集合
毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx毕业设计题目集合.docx
毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf毕业设计题目集合.pdf
目前最全的JAVA笔试题目集合 6、说出Servlet的生命周期,并说出Servlet和CGI的区别。 Servlet被服务器实例化后,容器运行其init方法,请求到达时运行其service方法,service方法自动派遣运行与请求对应的doXXX方法...
JAVA算法题目集合.pdf
acm入门题目集合
USACO 的题目集合,按第一个字母分类,包括原站点的算法说明文档