首页 > 试题广场 >

有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如

[问答题]
有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
/*
*比猫画虎,不成敬意。我测试了几次都可以哦!
*/
package number.action;

import java.util.ArrayList;
import java.util.List;

/*
 * @author snow
 * @time 2016_08_01 20:26
 * @questions 有两个有序的集合,集合的每个元素都是一段范围,求其交集,
 * 例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
 */
public class NumberIntersection_010 {
	public static void main(String args[]){
		Section section1 = new Section(2, 4);
		Section section2 = new Section(8,11);
		Section section3 = new Section(6,10);
		Section section4 = new Section(11,13);
		List<Section> aList = new ArrayList<Section>();
		List<Section> bList = new ArrayList<Section>();
		aList.add(section1);
		aList.add(section2);
		bList.add(section3);
		bList.add(section4);
		
		List<Section> result = getInterSection(aList,bList);
		System.out.println("两个集合的的交集是");
		for(Section sect:result){
			System.out.println(sect.getSection());
		}
	}

	private static List<Section> getInterSection(List<Section> aList,List<Section> bList) {
		int i = 0 , j = 0;
		List<Section> interSection = new ArrayList<Section>();
		while(i<aList.size()&&j<bList.size()){
			Section a = aList.get(i);
			Section b = bList.get(j);
			int aLeft = a.getLefe();
			int aRight = a.getRight();
			int bLeft = b.getLefe();
			int bRight = b.getRight();
			if(aLeft>bRight){
				j++;
			}else if(aRight<bLeft){
				i++;
			}else if(aLeft>bLeft){
				if(aRight<bRight){
					interSection.add(a);
					i++;
				}else{
					Section temp = new Section(aLeft,bRight);
					interSection.add(temp);
					j++;
				}
			}else{
				if(bRight<aRight){
					interSection.add(b);
					j++;
				}else{
					Section temp = new Section(bLeft,aRight);
					interSection.add(temp);
					i++;
				}
			}
		}
		return interSection;
	}
}

class Section{
	int lefe,right;
	public Section(int l,int r){
		lefe = l;
		right =r;
	}
	
	public int getLefe() {
		return lefe;
	}
	public int getRight() {
		return right;
	}

	public String getSection(){
		return "["+lefe + "," + right +"]";
	}
}

发表于 2016-08-01 21:51:29 回复(0)
import java.util.ArrayList;

public class RangeTest {

	public static void main(String[] args) {
		
		Range r1=new Range(4, 8);
		Range r2=new Range(9, 13);
		Range r3=new Range(6, 12);
		Range r4=new Range(7, 10);
		Range[] aR=new Range[]{r1,r2};
		Range[] bR=new Range[]{r3,r4};
		ArrayList<Range> result=getRangeSet(aR, bR);
		for(int i=0;i<result.size();i++){
			System.out.println(result.get(i));
		}
		
	}
	public static ArrayList<Range> getRangeSet(Range[] aR, Range[] bR){
		ArrayList<Range> ranges=new ArrayList<Range>();
		for(int i=0;i<bR.length;i++){
			for(int j=0;j<aR.length;j++){
				if(aR[j].right<bR[i].left){
					break;  //无交集
				}else if(aR[j].right>bR[i].left){
					int left=aR[j].left>bR[i].left ? aR[j].left:bR[i].left;   //选大的那个
					int right=aR[j].right<bR[i].right ? aR[j].right:bR[i].right;   //选小的那个
					Range range=new Range(left, right);
					ranges.add(range);
				}
			}
		}
		return ranges;
	}
}
class Range{
	int left;
	int right;
	public Range(int num1, int num2){
		left=num1;
		right=num2;
	}
	@Override
	public String toString() {
		return " [left=" + left + ", right=" + right + "]";
	}
	
}

发表于 2015-08-22 21:10:07 回复(4)
首先每个集合的元素数应该一致。
需要一个额外的辅助空间。
2个集合的第一个元素,第一个数字,取上限,第二个取下限。
发表于 2015-08-11 13:48:18 回复(1)
import java.util.ArrayList;

public class Baidu1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Section[] secA = new Section[2];
		secA[0] = new Section(4, 8);
		secA[1] = new Section(9, 13);
		Section[] secB = new Section[1];
		secB[0] = new Section(6, 12);
		ArrayList<Section> list = getInterSec(secA, secB);
		for(int i=0;i<list.size();i++){
			System.out.println(list.get(i).toString());
		}
	}
	
	public static ArrayList<Section> getInterSec(Section[] secA, Section[] secB) {
		ArrayList<Section> list = new ArrayList<Section>();
		for(int i=0;i<secA.length;i++){
			for(int j=0;j<secB.length;j++){
				if(secB[j].high < secA[i].low){
					break;
				}
				else{
					//生成新的交集
					int low = Math.max(secA[i].low, secB[j].low);
					int high = Math.min(secA[i].high, secB[j].high);
					Section newSec = new Section(low, high);
					list.add(newSec);
				}
			}
		}
		return list;
	}
}
class Section{
	int low;
	int high;
	public Section(int low, int high) {
		super();
		this.low = low;
		this.high = high;
	}
	@Override
	public String toString() {
		return "[low=" + low + ", high=" + high + "]";
	}	
}


编辑于 2016-09-28 14:05:53 回复(0)
import java.util.ArrayList;
/**
 * 有两个有序的集合,集合的每个元素都是一段范围,求其交集,
 * 例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
 * @author Cenby7
 */
public class Main {
	public static void main(String[] args) {
		/*int leftIndex=0;
		int rightIndex=0;*/
		ArrayList<Section> fist = new ArrayList<Section>();
		fist.add(new Section(4, 8));
		fist.add(new Section(8, 13));
		ArrayList<Section> second = new ArrayList<Section>();
		second.add(new Section(6, 12));
		second.add(new Section(11, 15));
		ArrayList<Section> result = new ArrayList<Section>();
		System.out.println(fist+" 交 "+second);
		//抽取重叠部分
		for (Section one: fist) {
			for(Section two : second){
				if(one.right<two.left){
					Section resultBean = new Section();
					//判断左边界
					resultBean.left = one.left<two.left ? two.left:one.left;
					//判断右边界
					resultBean.right = one.right<two.right ? one.right : two.right;
					result.add(resultBean);
				}
			}
		}
		System.out.println("混交:");
		System.out.println(result);
		System.out.println("合并:");
		ArrayList<Section> finalResult = new ArrayList<Section>();
		for (int i=0; i<result.size(); ) {
			int j;
			for(j=i+1; j<result.size() && result.get(i).right>=result.get(j).right; j++){
				//可以合并
				result.get(i).right = result.get(j).right;
			}
			finalResult.add(result.get(i));
			i=j;
		}
		System.out.println(finalResult);
	}
}
public class Section {
	public int left;
	public int right;
	
	public Section() {
		super();
	}
	public Section(int left, int right) {
		super();
		this.left = left;
		this.right = right;
	}
	@Override
	public String toString() {
		return "[" + left + "," + right + "]";
	}
	
}
不知道给定两个集合的元素,可不可以有重合。我的写法按可以重合的。
测试了几次是可以。没有去精简代码。求指教

发表于 2016-09-07 20:20:08 回复(0)
修改了一下楼上的答案:

import java.util.ArrayList;

public class RangeTest {
	
	public static void main(String[] args) {
		Range r1 = new Range(4, 8);
		Range r2 = new Range(9, 13);
		Range[] aR = new Range[]{r1,r2};
		
		Range r3 = new Range(6, 12);
		Range[] bR = new Range[]{r3};
		
		ArrayList<Range> result = getRangeSet(aR, bR);
		for (int i = 0; i < result.size(); i++) {
			System.out.println(result.get(i));
		}
		
	}
	
	public static ArrayList<Range> getRangeSet(Range[] aR,Range[] bR){
		ArrayList<Range> ranges = new ArrayList<Range>();
		for (int i = 0; i < bR.length; i++) {
			for (int j = 0; j < aR.length; j++) {
				if (aR[j].right<bR[i].left) {
					break;
				}else if (aR[j].right>bR[i].left) {
					int left=aR[j].left<bR[i].left?bR[i].left:aR[j].left;
					int right=aR[j].right>bR[i].right?bR[i].right:aR[j].right;
					Range range = new Range(left, right);
					ranges.add(range);
				}
			}
		}
		return ranges;
	}
	
}

class Range{
	
	int left,right;
	
	public Range(int _left,int _right) {
		this.left=_left;
		this.right=_right;
	}
	@Override
	public String toString() {
		
		return "[ left= "+left+" , "+" right= "+right+" ]";
	}
}
 

发表于 2016-08-01 15:32:47 回复(1)
//也不知道我的对不对大家运行看看吧,有错的说说,我也就随便瞎想的

package test;

import java.awt.List;
import java.util.ArrayDeque;
import java.util.ArrayList;

public class test1 {
    
    public static void main(String[] args) {        
        
        int [][]C = {{1,4},{5,9},{10,15},{16,19},{20,30}};
        int [][]D = {{3,6},{7,8},{9,12},{13,17}};
        int []ci = new int [C.length*2];
        int []di= new int [D.length*2];
        List lcd = new List();
        List isc = new List();
        int i=0,j=0;
        int ciLength=0,diLength=0;
        while(i < C.length)
        {
            ci[ciLength]=C[i][0];
            ciLength++;
            ci[ciLength]=C[i][1];
            ciLength++;
            i++;
        }
        while(j <D.length)
        {
            di[diLength]=D[j][0];
            diLength++;
            di[diLength]=D[j][1];
            diLength++;
            j++;
        }
        i=0;j=0;
        while(i<ci.length && j<di.length)
        {
            if(ci[i] > di[j])
            {
                lcd.add(""+di[j]);
                isc.add(""+false);
                j++;
            }else if(ci[i] < di[j])
            {
                lcd.add(""+ci[i]);
                isc.add(""+true);
                i++;
            }else if(ci[i] == di[j])
            {
                lcd.add(ci[i]+"");
                isc.add(""+true);
                lcd.add(di[j]+"");            
                isc.add(""+false);
                i++;
                j++;
            }
        }
        if(i == ci.length)
        {
            while(j < di.length)
            {
                lcd.add(di[j]+"");
                isc.add(""+false);
                j++;
            }
        }
        if(j == di.length)
        {
            while(i < ci.length)
            {
                lcd.add(""+ci[i]);
                isc.add(""+true);
                i++;
            }
        }
        int sum = lcd.getItemCount();
        int [][] CD = new int [C.length+D.length][2];
        int cdlength=0;
        int oushuC=0;
        int oushuD=0;
        for(int s=0;s<sum;s++)
        {
            if(Boolean.parseBoolean(isc.getItem(s)) != true)
            {//如果是b的话,开始寻找后序
                oushuD++;
                if(s+1 < sum)
                {
                    if(Boolean.parseBoolean(isc.getItem(s+1)) != true)
                    {//后一个也是b的
                        oushuD++;
                        if((oushuD%2 == 0))
                        {
                            CD[cdlength][0] = Integer.parseInt(lcd.getItem(s));
                            CD[cdlength][1] = Integer.parseInt(lcd.getItem(s+1));
                            cdlength++;
                        }
                        oushuD--;
                    }else{
                        //后一个是a
                        oushuC++;
                        if((oushuC%2) == 0 && (oushuD%2) != 0)
                        {                            
                            CD[cdlength][0] = Integer.parseInt(lcd.getItem(s));
                            CD[cdlength][1] = Integer.parseInt(lcd.getItem(s+1));
                            cdlength++;
                        }
                        oushuC--;
                    }

                }
            }else
            {//如果是a
                oushuC++;
                if(s+1 < sum)
                {
                    if(Boolean.parseBoolean(isc.getItem(s+1)) != true )//后一个b
                    {
                        //判断是开头的b还是结尾的b
                        oushuD++;
                        
                        if((oushuC%2)!=0 && (oushuD%2 == 0))//奇C,偶D
                        {
                            CD[cdlength][0] = Integer.parseInt(lcd.getItem(s));
                            CD[cdlength][1] = Integer.parseInt(lcd.getItem(s+1));
                            cdlength++;
                            
                        }
                        oushuD--;
                    }                    
                }
            }
        }
        //输出
        for(int l=0;l<cdlength;l++)
        {
                System.out.println(CD[l][0]+","+CD[l][1]);
        }
    }
}
发表于 2016-03-20 13:01:44 回复(0)
public class Test {
	public static void main(String[] args) {
		ArrayList<int[]> leftList=new ArrayList<int[]>();
		leftList.add(new int[]{4,8});
		leftList.add(new int[]{10,13});
		ArrayList<int[]> rightList=new ArrayList<int[]>();
		rightList.add(new int[]{6,7});
		rightList.add(new int[]{9,12});
		ArrayList<Integer> leftResult=new ArrayList<Integer>();
		ArrayList<Integer> rightResult=new ArrayList<Integer>();
		ArrayList<Integer> finalResult=new ArrayList<Integer>();
		for (int[] is : leftList) {
			for (int i = is[0]; i <= is[1]; i++) {
				leftResult.add(i);
			}
		}
		for (int[] is : rightList) {
			for (int i = is[0]; i <= is[1]; i++) {
				rightResult.add(i);
			}
		}
		loop:for (int i = 0; i < leftResult.size(); i++) {
			for (int j = 0; j < rightResult.size(); j++) {
				if (leftResult.get(i)==rightResult.get(j)) {
					finalResult.add(leftResult.get(i));
					continue loop;
				}
			}
		}
		int left=finalResult.get(0);
		int right=finalResult.get(0);
		System.out.print("["+left+",");
		for (int i = 0; i < finalResult.size(); i++) {
			if (finalResult.get(i)==right) {
				right++;
				if (i==finalResult.size()-1) {
					System.out.print(right-1+"]");
				}
				continue;
			}else {
				System.out.print(right-1+"]");
				left=finalResult.get(i);
				right=left;
				System.out.print("["+left+",");
				right++;
			}
		}
	}
}
这是一种非常直白的算法,甚至都不能称为算法,唯一的缺点是简单易想,思路是先将两边范围内所有的数字全部存储在不同的list中,然后进行比对,将相同的项存储在新的list中,然后输出边界
发表于 2016-02-26 17:02:23 回复(0)
<pre class="prettyprint lang-java">import java.util.Date; import java.util.LinkedList; import java.util.List; import java.util.Random; /** * A,B两个整数集合,设计一个算法求他们的交集,尽可能的高效。 */ public class test { public static int setSize = 1000000; public static int hashSize = setSize * 2; public static void main(String[] args) { // TODO Auto-generated method stub Integer A[] = new Integer[setSize]; Integer B[] = new Integer[setSize]; for(int i=0;i&lt;setSize;i++){ A[i]=(new Random().nextInt(setSize * 10)); B[i]=(new Random().nextInt(setSize * 10)); } System.out.println("赋值完毕"); long beginTime = System.currentTimeMillis(); Integer hashtable[] = new Integer[hashSize]; //现在将将A集合的数都放到hash表中,以数的hash值为下标,使用开放寻址法来解决冲突 //其实用拉链法更好 for(int i=0;i&lt;setSize;i++){ //取到需要存的数的下标 int index = A[i].toString().hashCode() % hashSize; if(index&lt;0){ index *= -1; } while(hashtable[index]!=null){ if(index &gt;= hashSize-1){ index=0; }else{ index++; } } hashtable[index] = A[i]; } List&lt;Integer&gt; result = new LinkedList&lt;Integer&gt;(); //开始对B for(int i=0;i&lt;setSize;i++){ //取到需要存的数的下标 int index = B[i].toString().hashCode() % hashSize; if(index&lt;0){ index *= -1; } while(hashtable[index]!=null){ if(hashtable[index] == B[i]){ result.add(B[i]); break; } if(index &gt;= hashSize-1){ index=0; }else{ index++; } } } if(result.size()!=0){ for(int i=0 ; i&lt;result.size();i++){ System.out.println(result.get(i)); } }else{ System.out.println("没有相同元素"); } System.out.println("计算耗时:"+ (System.currentTimeMillis() - beginTime)+" 毫秒"); } }</pre>
发表于 2015-08-21 11:42:07 回复(0)
先来看两个一般化的过程:A集合为{[a1,a2],[a3,a4]...},B集合为{[b1,b2],[b3,b4]...},对于B集合中的每个元素都去A集合中找和自己有关联的元素,如何是和自己有关联呢?
拿[a1,a2]和[b1,b2]来说,有以下几种情况:
1.a1<a2<b1<b2说明[a1,a2]和[b1,b2]没有关联,可以在A中去掉[a1,a2],继续和下一个元素比较
2.b1<b2<a1<a2说明[b1,b2]和A中最小的元素都没有关联,那么可以停止继续在A中的寻找
3.a1<b1<b2<a2说明他们公共区间为[b1,b2],此时可以停止在A中的继续寻找
4.a1<b1<a2<b2说明公共区间为[b1,a2],此时还需要继续和A中的下一个元素作比较
5.b1<a1<a2<b2说明公共区间为[a1,a2],此时还需要继续和A中的下一个元素作比较
6.b1<a1<b2<a2说明公共区间为[a1,b2],此时可以停止在A中的继续寻找
我们可以看到,[b1,b2]和A中所有元素比较的过程中结束条件为A遍历结束或者遇到2,3,6的情况,继续选择B中的下一个元素,如此直至B遍历完。
时间复杂度O(n^2)
发表于 2015-08-20 16:47:13 回复(0)
import java.util.ArrayList;
import java.util.List;
class Section {
         int left,right;
    public Section(int l, int r){
        this.left = l;
        this.right =r;
    }
    public int getLeft(){
        return this.left;
    }
    public int getRight(){
        return this.right;
    }
    @Override
    public String toString(){
        return "["+this.left+","+this.right+"]";
    }
}
public class ListRe {
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        // 直接复制的
        Section section1 = new Section(2, 4);
        Section section2 = new Section(8,11);
        Section section3 = new Section(6,10);
        Section section4 = new Section(11,13);
        List<Section> aList = new ArrayList<Section>();
        List<Section> bList = new ArrayList<Section>();
        aList.add(section1);
        aList.add(section2);
        bList.add(section3);
        bList.add(section4);
        List<Section> result = getInterSection(aList,bList);
        System.out.println("两个集合的的交集是");
        for(Section sect:result){
            System.out.println(sect.toString());
        }
    }
    
    // 时间复杂度为n
    public static List<Section> getInterSection(List<Section> aList, List<Section> bList){
        List<Section> interSection = new ArrayList<Section>();
        int a = aList.size();
        int b = bList.size();
        int i=0,j=0;
        while(i<a&&j<b){
            // 根据下标取对应项
            Section aSection = aList.get(i);
            Section bSection = bList.get(j);
            // 右值落后者对应下标+1
            if(aSection.right<bSection.right){
                i++;
            }else{
                j++;
            }
            // 取左值里大的
            int tl = aSection.left>bSection.left ? aSection.left: bSection.left;
            // 取右值里小的
            int tr = aSection.right<bSection.right ? aSection.right: bSection.right;
            // 左值<=右值时取到交集
            if(tl<=tr){
                interSection.add(new Section(tl, tr));
            }
        }    
        return interSection;
    }
}

发表于 2019-08-02 23:32:46 回复(0)
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String args[]) {
        int[][] num1 = { { 4, 8 }, { 9, 13 } };
        int[][] num2 = { { 6, 12 } };
        int len1 = num1.length;
        int len2 = num2.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                int num_1[] = num1[i];
                int num_2[] = num2[j];
                int[] temp = new int[2];
                if (num_1[0] > num_2[1] || num_1[1] < num_2[0]) {
                    continue;
                } else {
                    if (num_2[0] > num_1[0] && num_2[0] < num_1[1]) {
                        temp[0] = num_2[0];
                    } else if (num_1[0] > num_2[0] && num_1[0] < num_2[1]) {
                        temp[0] = num_1[0];
                    }
                    if (num_2[1] > num_1[1] && num_2[0] < num_1[1]) {
                        temp[1] = num_1[1];
                    } else if (num_1[1] > num_2[1]) {
                        temp[1] = num_2[1];
                    }
                    list.add(temp);
                }
            }
        }
        System.out.print("{");
        for (int i = 0; i < list.size(); i++) {
            System.out.print("[" + list.get(i)[0] + "," + list.get(i)[1] + "]");
        }
        System.out.print("}");
    }
}

发表于 2017-09-23 20:13:29 回复(0)
package Jack;

import java.util.ArrayList;
import java.util.List;

/** 
 * TODO(这里用一句话描述这个类的作用) 
 *
 * @author Jack
 * @date 2017年9月19日 下午4:00:58 
 * @version
V1.0  
 */
public class Jihe {

    public List<Yuansu> jihe;
    
    public Jihe(){
        jihe = new ArrayList<>();
    }
    
    public void addYuansu(Yuansu yuansu){
        jihe.add(yuansu);
    }
    
    public Yuansu getYuansu(int index){
        return jihe.get(index);
    }
    
    
    
    public static void main(String[] args) {
        Jihe jihe1 = new Jihe();
        Jihe jihe2 = new Jihe();
        Yuansu yuansu1 = new Yuansu(4, 8);
        Yuansu yuansu2 = new Yuansu(9, 13);
        Yuansu yuansu3 = new Yuansu(6, 9);
        Yuansu yuansu4 = new Yuansu(10, 15);
        jihe1.addYuansu(yuansu1);
        jihe1.addYuansu(yuansu2);
        jihe2.addYuansu(yuansu3);
        jihe2.addYuansu(yuansu4);
        
        int i = 0, j = 0;;
        for(;i<jihe1.jihe.size();i++){
            for(;j<jihe2.jihe.size();j++){
                int a = jihe1.getYuansu(i).firData;
                int b = jihe1.getYuansu(i).secData;
                int a1 = jihe2.getYuansu(j).firData;
                int b1 = jihe2.getYuansu(j).secData;
                if(a < a1 && b > a1 &&  b < b1){
                    System.out.print("["+a1+","+b+"]  ");
                    break;
                }else if (a < a1 && a1 < b && b1 < b) {
                    System.out.print("["+a1+","+b1+"]  ");
                }else if(a > a1 && b < b1){
                    System.out.print("["+a+","+b+"]  ");
                    break;
                }else if (a > a1 && b > b1) {
                    System.out.print("["+a+","+b1+"]  ");
                }else if(b < a1){
                    break;
                }else if(a > b1){
                    
                }
                        
            }
        }
        
    }
}

class Yuansu{
    
    int firData;
    int secData;
    
    public Yuansu(int firDate,int secData){
        this.firData = firDate;
        this.secData = secData;
    }
}

发表于 2017-09-19 16:43:56 回复(0)
//求测试样例来测试,,,,尽情测吧
import java.util.Scanner;

/**
 * 题目描述
有两个有序的集合,集合的每个元素都是一段范围,求其交集,
例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
 *
 */
public class Main {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		System.out.println("请输入第一个集合的元素个数:");
		int m=scanner.nextInt();
		int []first_set = new int[2*m];
		System.out.format("请输入%s个元素的范围",m);
		for(int i=0;i<2*m;i+=2){
			first_set[i]=scanner.nextInt();
			first_set[i+1]=scanner.nextInt();
		}
		System.out.println("请输入第二个集合的元素个数:");
		int n=scanner.nextInt();
		//int []second_set = new int[2*n];
		int left,right,intersection_left,intersection_right;
		for(int j=0;j<n;++j){
			left=scanner.nextInt();
			right=scanner.nextInt();
			//开始将第二个集合中的元素与第一个集合中所有元素求交集
			for(int i=0;i<2*m;i+=2){
				intersection_left=left>first_set[i]?left:first_set[i];
				intersection_right=right>first_set[i+1]?first_set[i+1]:right;
				if(intersection_left<intersection_right){
					System.out.format("[%s,%s]", intersection_left,intersection_right);
				}
			}
		}
	}
}


编辑于 2017-08-12 11:40:49 回复(0)
//集合求交集后只会划分为比原来两个集合都小的集合。所以只需要两层遍历,用第一个集合的每个区间与第二个集合的每个区间求交集即可。
import java.util.ArrayList;  public class MergeSet {  public static void main(String[] args) {
      int[][] set1 = {{4,8},{9,13}};
       int[][] set2 = {{6,12}};
      ArrayList<int[]> res = new ArrayList<>();  for (int i = 0; i < set1.length; i++) { for (int j = 0; j < set2.length; j++) { if(set1[i][0]>set2[j][1]||set1[i][1]<set2[j][0])continue;
       else {  int[] now = new int[2];    now[0]=Math.max(set1[i][0],set2[j][0]);
       now[1]=Math.min(set1[i][1],set2[j][1]);
      res.add(now);    }
            }
        }  for (int i = 0; i < res.size(); i++) {
            System.out.println("["+res.get(i)[0]+","+res.get(i)[1]+"]");    }
    }
}

编辑于 2017-08-12 01:13:16 回复(0)
import java.util.ArrayList;

public class Main {

/**
* 有两个有序的集合,集合的每个元素都是一段范围,求其交集,
* 例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
*/
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
list1.add(4);
list1.add(8);
list2.add(6);
list2.add(12);
System.out.println(getList(list1,list2));
}
public static ArrayList<Integer> getList(ArrayList<Integer> list1 ,ArrayList<Integer> list2){
ArrayList<Integer> list = new ArrayList<Integer>();
int start = 0;
int end = 0;
int  a = list1.get(0);
int  b = list1.get(1);
int  c = list2.get(0);
int  d = list2.get(1);
if(b<c|| a>d){
return null;
}
//a>=c  b<=d
if(a>=c & b<=d){
start = a;
end   = b;
}
//c>=a d<=b
if(c>=a &d<=b){
start = c;
end   = d;
}
//
if(c>=a & b>=c & b<=d){
start = c;
end   = b;
}
//
if(a>=c & d>=a & d<=b){
start = a;
end   = d;
}
list.add(start);
list.add(end);
return list ;
}

}
发表于 2017-08-10 19:14:40 回复(0)
先把每个集合中的范围求好,因为集合中有的范围可能是重复的。
对集合进行合并:即根据每个元素的起点排序,再从头到尾遍历一遍,标记上一个合并后的元素为last(初始化为0),对i=1~n-1,有start[last]<start[i]:若end[last]<start[i],则last=i,新起一段范围;若end[last]<end[i] ,则合并后元素的范围起点终点为start[last],end[i];否则, 合并后元素的范围起点终点 为start[last],end[ last ]。排序和遍历的总的复杂度为O(nlogn)。n为集合大小。

然后用指针i和指针j分别从头遍历两个集合。
完全覆盖关系:若start[i]<=start[j]<=end[j]<=end[i],则重合的有start[j],end[j],把它加入新的集合,j++;若 start[j]<=start[i]<=end[i]<=end[j],则把start[i],end[i]加入新的集合,i++;
部分重叠:若 start[i]<=start[j]<=end[i]<=end[j],重叠部分是start[j],end[i],然后i++;i,j交换也成立
没有重叠:若start[i]<end[i]<start[j]<end[j],则i++;i、j交换也成立
这部分的复杂度是O(n)

因此总体时间复杂度是O(nlgn)。

发表于 2017-03-23 22:32:07 回复(0)
a = [[4,8],[9,13]]
b = [[6,12]]
merge = []
for i in a:
    for j in b:
        if (j[0]<=i[0] and j[1]>=i[0]):
            merge.append([i[0],min(i[1],j[1])])
        elif j[0]>=i[0] and j[0]<=i[1]:
            merge.append([j[0],min(i[1],j[1])])
print merge

发表于 2017-02-25 21:40:48 回复(0)
package com.wangyi.test2015;

import java.util.ArrayList;

class Range {
	public int prev;
	public int last;

	public Range(int prev, int last) {
		this.prev = prev;
		this.last = last;
	}

	public Range inter(Range other) {
		if (this.prev > other.last || this.last < other.prev)
			return null;
		else if (this.last >= other.prev && this.prev <= other.prev)
			return new Range(other.prev, this.last);
		else if (this.prev >= other.prev && this.last <= other.last)
			return this;
		else if (other.last >= this.prev && other.prev <= this.prev)
			return new Range(this.prev, other.last);
		else if (other.prev >= this.prev && other.last <= this.last)
			return other;
		return null;
	}

	@Override
	public String toString() {
		return "Range [prev=" + prev + ", last=" + last + "]";
	}
	
}

public class Main2 {
	public static void main(String[] args) {
		ArrayList<Range> list = new ArrayList<Range>();
		list.add(new Range(4, 8));
		list.add(new Range(9, 13));
		ArrayList<Range> otherList = new ArrayList<Range>();
		otherList.add(new Range(6, 12));
		ArrayList<Range> newList = new ArrayList<Range>();
		for (Range range : list) {
			for (Range otherRange : otherList) {
				if (range.inter(otherRange) != null)
					newList.add(range.inter(otherRange));
			}
		}
		
		for (Range range : newList) {
			System.out.println(range);
		}
	}
}

发表于 2016-09-12 12:21:18 回复(0)
importjava.util.LinkedList;
importjava.util.List;
publicclassMain {
    publicstaticList<intersection> getIntersection(List<intersection> a, List<intersection> b) {
        List<intersection> inter = newLinkedList<intersection>();
        //遍历a中的所有数组
        for(inti = 0; i < a.size(); i++){
            //遍历b中的所有数组
            for(intj = 0; j < b.size(); j++) {
                //按照我们的规定的比较方法。如果把前边界小的排到前面
                if(a.get(i).left <= b.get(j).left){
                    //如果前边界大区域的前边界大于前边界小的区域的后边界,有交集。
                    if(b.get(j).left < a.get(i).right){
                        //确定前边界,后边界
                        intleft = b.get(j).left;
                        intright = a.get(i).right > b.get(j).right ? b.get(j).right : a.get(i).right;
                        intersection intsction = newintersection(left,right);
                        inter.add(intsction);
                    }
                }else{
                    if(a.get(i).left < b.get(j).right){
                        //确定前边界,后边界
                        intleft = a.get(i).left;
                        intright = a.get(i).right > b.get(j).right ? b.get(j).right : a.get(i).right;
                        intersection intsction = newintersection(left,right);
                        inter.add(intsction);
                    }
                }
            }
        }
        returninter;
    }
    publicstaticclassintersection{
        intleft;
        intright;
        publicintersection(intleft, intright) {
            super();
            this.left = left;
            this.right = right;
        }
        @Override
        publicString toString() {
            return"intersection [left="+ left + ", right="+ right + "]";
        }
    }
}

发表于 2016-08-15 15:28:46 回复(0)