/* *比猫画虎,不成敬意。我测试了几次都可以哦! */ 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 +"]"; } }
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 + "]"; } }
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 + "]"; } }
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 + "]"; } }
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+" ]";
}
}
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中,然后输出边界
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;}@Overridepublic 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());}}// 时间复杂度为npublic 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);// 右值落后者对应下标+1if(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;}}
import java.util.ArrayList;import java.util.List;
//求测试样例来测试,,,,尽情测吧 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); } } } } }
//集合求交集后只会划分为比原来两个集合都小的集合。所以只需要两层遍历,用第一个集合的每个区间与第二个集合的每个区间求交集即可。
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]+"]"); } } }
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); } } }
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;}@OverridepublicString toString() {return"intersection [left="+ left + ", right="+ right + "]";}}}