精华内容
下载资源
问答
  • 区间求交集

    2018-03-16 16:12:30
    题目:有两个有序的集合,集合的每个元素都是一段范围,交集,例如集合A:{[4,8],[9,13]} 和 集合B:{[6,12]}的交集为 {[6,8],[9,12]}c语言实现:#include <stdio.h>typedef struct sec_tag{ ...

    题目:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合A:{[4,8],[9,13]} 和 集合B:{[6,12]}的交集为 {[6,8],[9,12]}

    c语言实现:

    #include <stdio.h>


    typedef struct sec_tag
    {
    double start;
    double end;
    } sec;


    #define min(a,b) (((a)<(b))?(a):(b))
    #define max(a,b) (((a)>(b))?(a):(b))


    //0表成功,非0表失败
    int intersec(sec s1,sec s2,sec *res);
    //len:数组长度,prefix_info:输出数字前要输出的字符串,presion小数点后保留位数
    void printout(sec *pset,int len,char* prefix_info,int presion);


    int main()
    {
    sec set1[4]={{6,8},
    {9,23},
    {25,27},
    {29,48}
    };
    sec set2[5]={{7,10},
    {11,15},
    {17,33},
    {35,39},
    {42,50}
    };
    sec set3[9]={0}; //存放取交集的结果
      sec sec1,sec2,sec3;
    int index1=0;
    int index2=0;
    int index3=0;
    int err=0;


    do 
    {
    sec1=set1[index1];
    sec2=set2[index2];
    err=intersec(sec1,sec2,&sec3);
    if(err<0)
    {
    index1++;
    }
    else if(err==0)
    {
    set3[index3]=sec3;
    index3++;
    if(sec3.end==sec1.end)
    index1++;
    else //if(sec3.end==sec2.end)
    index2++;
    }
    else if(err>0)
    {
    index2++;
    }
    } while(index1<4 && index2<5);
    printout(set1,4,"集合1:\t\t",0);
    printout(set2,5,"集合2:\t\t",0);
    printout(set3,9,"求交集的结果:\t",0);
    getchar();
    }


    //0表成功,非0表失败
    int intersec(sec s1,sec s2,sec *res)
    {
    res->start=res->end=0;
    if(s1.end<=s2.start) //s1在s2的左边,没有交集
    return -1;
    if(s1.start>=s2.end) //s1在s2的右边,没有交集
    return 1;
    res->start=max(s1.start,s2.start);
    res->end=min(s1.end,s2.end);
    return 0;
    }


    //len:数组长度,prefix_info:输出数字前要输出的字符串,presion小数点后保留位数
    void printout(sec *pset,int len,char* prefix_info,int presion)
    {
    int i=0;
    char format[20]="{%f,%f}\t";


    if(prefix_info!=NULL)
    printf("%s",prefix_info);


    if(presion>=0)
    sprintf(format,"{%%.%df,%%.%df}\t",presion,presion);


    for(;i<len;i++)
    {
    printf(format,pset[i].start,pset[i].end);
    }
    printf("\n");
    }

    展开全文
  • N个区间求交集

    千次阅读 2018-07-30 11:14:53
    博主遇​​到一个问题,要对文章根据用户阅读记录进行... 最终博主想到了一个优化策略,在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重,这时就涉及到对用...

          博主遇​​到一个问题,要对文章根据用户阅读记录进行去重,但用户阅读记录的文章ID最长可以达到300条,然后在数据库中使用NOT  IN语句在查询时对文章进行去重,但是这样操作在记录比较长时,语句执行效率极其低下,

           最终博主想到了一个优化策略,在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重,这时就涉及到对用户的阅读文章ID区间进行求交集的操作,具体求交集思路见代码:

    import java.util.*;
    
    
    public class Main {
    
        public static boolean union(Set<String> set) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
          /*测试运行效率*/
            Random random = new Random();
            Set<String> set = new HashSet<String>();
            for (int i = 0; i < 100000; i++) {
                String insStr = "";
                int num = random.nextInt(10000000);
                insStr = random.nextInt(num) + "," + num;
                set.add(insStr);
            }
            /*测试准确性*/
            set.add("0,15");
            set.add("8,15");
            set.add("6,7");
            set.add("100,150");
            set.add("12,85");
            set.add("4,10");
            set.add("5,16");
    
            System.out.println("0.0 " + new Date().getTime());
            while (union(set)) {
            }
            System.out.println("-.- " + new Date().getTime());
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
    }

    优化代码:后期博主需要获取最大值 并对过小的值进行合并整合  故而优化方法如下(该优化弃用) ;

    /**
         * 合并所有集合 并返回最大值
         * @param set
         * @param max
         * @return
         */
        public static Long union(Set<String> set ,Long max) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                if (Long.parseLong(arr[1]) > max) {
                    max = Long.parseLong(arr[1]);
                }
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
                            max = union(set , max);
                            return max;
                        }
                    }
                }
            }
            return max;
        }
    

    博主对上面的代码进行大数据(10W+区间)测试后,发现会出现堆栈错误,递归调用太多,线程池满了;

    重新优化代码后 耦合度增加  但减少运算次数

    import java.util.*;
    
    
    public class Main {
    
        /**
         * 合并所有集合 并返回最大值
         *
         * @param set
         * @param max
         * @return
         */
        public static Long union(Set<String> set, Long max) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                if (Long.parseLong(arr[1]) > max) {
                    max = Long.parseLong(arr[1]);
                }
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
    //                        max = union(set , max);
                            return max;
                        }
                    }
                }
            }
            return -1L;
        }
    
        public static void removeSmall(Set<String> set) {
            Iterator<String> it = set.iterator();
            Long min = 0L;
            Long max = 0L;
            while (it.hasNext()) {
    
            }
        }
    
        public static void main(String[] args) {
            /*测试运行效率*/
            Random random = new Random();
            Set<String> set = new HashSet<String>();
            for (int i = 0; i < 100000; i++) {
                String insStr = "";
                int num = random.nextInt(10000000);
                insStr = random.nextInt(num) + "," + num;
                set.add(insStr);
            }
            /*测试准确性*/
            set.add("0,15");
            set.add("8,15");
            set.add("6,7");
            set.add("100,200");
            set.add("12,85");
            set.add("4,10");
            set.add("5,16");
    
            System.out.println("0.0 " + new Date().getTime());
            Long max = 0L;
            for(Long tempMax=max; (tempMax = union(set, max)) >= 0 ; )
            {
                max = tempMax;
            }
            System.out.println("MAX = " + max);
            System.out.println("-.- " + new Date().getTime());
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
        }
    }

     

    展开全文
  • 有序区间求交集算法

    千次阅读 2018-08-29 18:13:24
    题目描述:有两个有序的集合,集合的每个元素都是一段范围,交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。 我们知道,两个集合的交集必定是去满足范围小的那个集合,因此此题的解法就是每次...

    题目描述:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。

    我们知道,两个集合的交集必定是去满足范围小的那个集合,因此此题的解法就是每次寻找一个小的范围。那么,关键之处就在于如何寻找这个范围。

    如下图所示,两个集合{[2,8],[9,14]}和{[1,10],[12,15]}:

    集合示例
    集合示例

    集合从左到右进行扫描,每次选取边界的时候都是去选取值小的边界,假设两个数组的索引分别为i和j并指向起始位置。

    • 1<2,选1,索引j向后移动,此时i指向2,j指向10;
    • 2<10,选2,索引i向后移动,此时i指向8,j指向10;
    • 8<10,选8,找到一个右边界,[2,8]为其中一个结果,索引i向后移动,此时i指向9,j指向10;

    以此类推……

    那么,什么时候确定为一个结果子集呢?

    由于扫描为从左到右扫描,开始扫描的时左边界,每次总是取边界中值较小的边界,我们要去寻找一个右边界,因此达到一左一右的状态时,即为一个结果子集。但是,这里有一个重要的地方就是判断结果是否正确。比如上面的例子中,选择1之后的索引达到了一左一右的状态,但是[2,10]并不是我们想要的。在我们选2之后,选8之前,i和j分别指向8和10,即在确定右边界之前,必定要达到两个集合的索引同时达到右边界,然后对两个右边界加以判断。因此需要加一个标志,去判断确定右边界之前是否同时达到右边界。

    public class SetIntersection {
    
    	private void intersection(int[] a, int[] b) {
    		int len1 = a.length, len2 = b.length;
    		int flag = 0, i = 0, j = 0;
    		int pre1 = 0, pre2 = 0;
    		while (i < len1 && j < len2) {
    			pre2 = pre1;
    			if (i % 2 == 1 && j % 2 == 1) {
    				flag = 1;
    			} else {
    				flag = 0;
    			}
    			if (a[i] < b[j]) {
    				pre1 = a[i++];
    			} else {
    				pre1 = b[j++];
    			}
    			if (flag == 1 && ((i % 2 == 0 && j % 2 == 1) || (i % 2 == 1 && j % 2 == 0))) {
    				System.out.println(pre2 + " " + pre1);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		int a[] = { 2, 8, 9, 14, 15, 20, 22, 25 };
    		int b[] = { 1, 10, 12, 16, 19, 25, 30, 40 };
    		new SetIntersection().intersection(a, b);
    	}
    }

    这里我们将两个集合的边界有序地放到了数组里面,下面是程序的输出结果。

    有兴趣的朋友可以自己试着改进一下我的算法。

     

     

     

     

    展开全文
  • 如下所示:  1 3 4 9 11 13 n1段区间之间互无交集,|——| |——————| |————|

    如下所示:

                                            1      3        4                    9             11            13

    n1段区间之间互无交集,|——|        |——————|               |————|                                         

    n2段区间之间互无交集       |————|     |——|   |————|              |——————|

                                                2            5     6     7   8            10           12                  14

    仅通过图示来看很容易得到交集的答案,交集是[2,3], [4,5],  [6,7],  [8,9],  [12,13],但是当区间很多时如何去求?


    首先定义两个List<Long> list1=new ArrayList<Long>();   List<Long> list2=new ArrayList<Long>();

    list1放置n1段区间的起始终止点 :list1.add(1);list1.add(3);...

    list2放置n2段区间的起始终止点:list2.add(2);list2.add(5);.....

    然后调用函数:

    public List<Long> GetIntersection(List<Long> list1, List<Long> list2){
    		List<Long> intersection=new ArrayList<Long>();
    		
    		for(int i=0;i<list1.size();i+=2){
    			Long start1=list1.get(i);  Long end1=list1.get(i+1);
    			for(int j=0;j<list2.size();j+=2){
    				Long start2=list2.get(j);  Long end2=list2.get(j+1);
    				//  |______|                                   |______|
    				//             |______|     or        |______|
    				if(end1<=start2 || end2<=start1){continue;}
    				if(start2>start1){				    
    					if(end1<end2){
    					    //  |______|
    						//       |______|
    						intersection.add(start2);  intersection.add(end1);						
    					}else{
    						//  |______|
    						//    |____|
    						intersection.add(start2);  intersection.add(end2);	
    					}
    				}else{
    					if(end1<end2){
    					    //      |___|
    						//     |______|
    						intersection.add(start1);  intersection.add(end1);						
    					}else{
    						//       |______|
    						//    |____|
    						intersection.add(start1);  intersection.add(end2);	
    					}
    				}
    			}
    		}
    		return intersection;
    	}


    展开全文
  • 区间排列求交集

    2020-09-07 08:29:55
    两组多区间排列求交集 两个区间求交集问题,在数学问题上有好几种情况: 例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]} 区间A和区间B完全没有交集区间A和区间B有部分交集区间A和区间B,其中一个为...
  • r),一些区间使得这些区间交集是该m区间的并集。 分析: 经分析将m个区间排序,易知答案即是: 第一个区间的l与最后一个区间的r形成的区间、第二个区间的l与第一个区间的r形成的区间、第三个区间的l与第而个...
  • 用算法优雅地出两组区间交集

    千次阅读 2019-09-13 01:17:38
    预计阅读时间:4 分钟本文是区间系列问题的第三篇,前两篇分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间交集。先看下题目,LeetC...
  • 判断两个区间有无交集

    千次阅读 2020-06-30 14:33:53
    有两个区间A[a1,b1], B[a2,b2],判断这两个区间有没有交集 思路就是如果两个区间不相交,那么最大的开始端一定大于最小的结束端 if(max(a1, a2) < min(b1, b2)){ return "有交集" }else{ return "无交集" } ...
  • 区间交集

    千次阅读 2019-08-01 15:40:15
    区间交集 #include <bits/stdc++.h> using namespace std; int main() { int n, ans = 0; // ans存储最终结果 scanf("%d", &n); vector<pair<int, int>> v1(n), v2(n); //分别存储两个区间...
  • 目的:范围/区间交集 A 和 B 两个闭区间的写法作为向量 [lowerbound1 upperbound1 lowerbound2 upperbound2] 或作为矩阵[下界1,下界2,下界n; 上界1、上界2、上界n] A 和 B 必须按升序排序 out 是数学交集 A n B ...
  • 点击上方蓝字设为星标东哥带你手把手撕力扣~作者:labuladong 公众号:labuladong若已授权白名单也必须保留以上来源信息本文是区间系列问...
  • 3 区间交集

    2021-05-06 23:05:46
    986. 区间列表的交集 给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。 ...
  • 区间调度之区间交集问题 区间调度问题共写了3片博客,前两篇重叠区间和区间合并分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间的交集。 一、解题思路 解决区间问题的思路...
  • 1.区间列表求交集、差集、并集 比如区间列表{[10-100],[120-200]} 减去 {[50-60],[65-70],[75-80]} 用代码怎么实现? 已经写了两个区间之间的计算方法,代码如下,但是列表相减会出现问题,有没有大佬解决过类型...
  • 两个区间存在交集

    2018-02-24 10:28:00
    存在区间[a1,b1]和[a2, b2],当满足什么条件时,两个区间交集? !(b1<a2 or b2<a1) 或 b1>=a2 and b2>=a1 转载于:https://www.cnblogs.com/allenwas3/p/8464385.html...
  • 我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。这么一想,我好像也...
  • mysql如何编写sql语句 ,两个时间区间交集!!! 这是鄙人的第一篇博客!只代表自己的观点和看法,大神请绕路或指导! 为什么会写这样的一篇博客呢? 在项目里遇到一个这样需求点!一个工单可以分配多个安装...
  • 两条区间交集∩和并集∪

    千次阅读 2017-07-21 14:42:24
    这两个例子也就列举了这两个情况,所示两个区间并集的关键就是判断两个区间是否有交集 下面的就写代码了 clc;clear;close all %% 两个区间的并集 a = [1398.7, 1404.7]; b = [1405.0, 1408.7]; endPoints ...
  • 题意:给你n段区间,让你这些区间的...分析:求区间交集: 假如min(a[i],b[i]) &lt; max(a[i - 1],b[i - 1]) 那么continue; 现在考虑两种情况: (1)if(a[i] == b[i]) 那么我们计算a[i],,b[i]前边的交集...
  • 区间列表的交集 给定两个由一些 闭区间 组成的列表,每个区间列表都是成对不相交的,并且已经排序。 返回这两个区间列表的交集。 (形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,016
精华内容 10,406
关键字:

区间求交集