-
区间求交集
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");
} -
区间求交集算法
2016-03-12 21:46:14最近要去网易笔试,做往年笔试题的时候遇到一个比较难搞的,原题:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]} 在网上看了一下没有比较巧妙...最近要去网易笔试,做往年笔试题的时候遇到一个比较难搞的,原题:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}
在网上看了一下没有比较巧妙地解决方案,于是自己想了一个,思路如下,我假设了两个区间集合A{[2,4],[8,14],[15,20],[22,25]},B{[1,5],[8,16],[19,25],[30,40]}
将这两个集合表示在图上就是下面这样子的:
我们可以画一条线,这条线是假想的,你可以把这条线想象是一个传感器,它能统计穿过了多少个点,比如下图线就是有一个点穿过了线。
这样我们就能通过穿过线的点的个数来判断是否区间重合了。我们有结论,当穿过线的点多余一个的时候(必须有两个点,一个来自A,一个来自B)那么区间重合,这条线有一个专业名词叫做扫线,这名字很形象。
好的,思路讲完了,直接看代码:
public class SetSort {
//声明两个数组,分别表示集合A,B
ArrayList<Range> ralist = new ArrayList<Range>();
ArrayList<Range> rblist = new ArrayList<Range>();
//这里是初始化一下数据,没啥可说的
public void DataInial() {
Range r1 = new Range();
r1.left = 2;
r1.right = 4;
Range r2 = new Range();
r2.left = 8;
r2.right = 14;
Range r3 = new Range();
r3.left = 15;
r3.right = 20;
Range r4 = new Range();
r4.left = 22;
r4.right = 25;
Range r5 = new Range();
r5.left = 1;
r5.right = 5;
Range r6 = new Range();
r6.left = 8;
r6.right = 16;
Range r7 = new Range();
r7.left = 19;
r7.right = 25;
Range r8 = new Range();
r8.left = 30;
r8.right = 40;
ralist.add(r1);
ralist.add(r2);
ralist.add(r3);
ralist.add(r4);
rblist.add(r5);
rblist.add(r6);
rblist.add(r7);
rblist.add(r8);
}
public static void main(String[] args) {//交集集合
ArrayList<Range> list = new ArrayList<Range>();
SetSort ss = new SetSort();
ss.DataInial();
list = Help.FindRange(ss.ralist, ss.rblist);
for (Range r : list) {
System.out.println("[" + r.left + "," + r.right + "]");
}
}
}
class Help {
public static ArrayList<Range> FindRange(ArrayList<Range> ra, ArrayList<Range> rb) {
int max = 0;//这个值表示count所要循环的上界
ArrayList<Range> rclist = new ArrayList<Range>();//交集的集合
if (ra.get(ra.size() - 1).right > rb.get(rb.size() - 1).right) {
max = rb.get(rb.size() - 1).right;
} else {
max = ra.get(ra.size() - 1).right;
}
int count = 0;//这个值就是扫线的坐标
if (ra.get(0).left > rb.get(0).left) {
count = ra.get(0).left;
} else {
count = rb.get(0).left;
}
int left = 0;
int right = 0;
boolean flage = false;
//核心算法
for (; count < max+1; count++) {
//如果扫线刚好有两个点穿过,则记载第一次的值,作为区间的左值,当穿过扫线的点由多个变为一个或者0个的时候,//则记录正要变化的那个count的值作为区间的右值
//这里面的flage用来防止重复赋值给区间
if (IS_ELEMENT(ra, count) && IS_ELEMENT(rb, count)) {
if (!flage) {
left = count;
flage = true;
}
} else {
if (flage) {
right = count;
flage = false;//new一个区间,添加到交集集合中去
rclist.add(new Range(left, right));
}
}
}
return rclist;
}
//这个方法用来判断,当前扫线的值,是否在集合某个元素中
public static boolean IS_ELEMENT(ArrayList<Range> list, int count) {
boolean flag = false;
for (int i = 0; i < list.size(); i++) {
if (list.get(i).right <= count) {
continue;
}
if (list.get(i).left > count) {
break;
}
if (list.get(i).left <= count && list.get(i).right >= count) {
flag = true;
break;
}
}
return flag;
}
}
//数组中的元素结构
class Range {
public Range() {
}
int right = 0;
int left = 0;
public Range(int left, int right) {
this.right = right;
this.left = left;
}
}这个算法想了好几个小时,总算是想出来了,其实这个算法有个缺点,就是当集合中的区间比较少,但是区间长度比较大的时候,count会循环很多次,比如A{[2,6],[10,100000]};B{[3,8],[9,100000]}这个区间的交集是[3,6],[10,100000]这意味着count需要循环100000次左右,这是非常浪费的。有兴趣的朋友可以自己试着改进一下我的算法。
-
有序区间求交集算法
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); } }
这里我们将两个集合的边界有序地放到了数组里面,下面是程序的输出结果。
有兴趣的朋友可以自己试着改进一下我的算法。
-
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()); } } }
-
算法 n1段区间 与 n2段区间求交集
2017-08-13 03:07:01如下所示: 1 3 4 9 11 13 n1段区间之间互无交集,|——| |——————| |————| -
多区间排列求交集
2020-09-07 08:29:55两个区间求交集问题,在数学问题上有好几种情况: 例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]} 区间A和区间B完全没有交集。 区间A和区间B有部分交集。 区间A和区间B,其中一个为另一个的子集。 区间A... -
用算法优雅地求出两组区间的交集
2019-09-13 01:17:38预计阅读时间:4 分钟本文是区间系列问题的第三篇,前两篇分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间的交集。先看下题目,LeetC... -
如何优雅地求出两组区间的交集
2020-03-18 07:20:00点击上方蓝字设为星标东哥带你手把手撕力扣~作者:labuladong 公众号:labuladong若已授权白名单也必须保留以上来源信息本文是区间系列问... -
现在有一个需求,多个区间值求交集、并集、差集。
2019-08-28 17:30:441.区间列表求交集、差集、并集 比如区间列表{[10-100],[120-200]} 减去 {[50-60],[65-70],[75-80]} 用代码怎么实现? 已经写了两个区间之间的计算方法,代码如下,但是列表相减会出现问题,有没有大佬解决过类型... -
七十二、区间合并,插入求交集, 删除被覆盖区间
2020-09-29 23:58:14我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。这么一想,我好像也... -
求两条区间的交集∩和并集∪
2017-07-21 14:42:24求交集 求两条一直线段的重合部分,也就是求两个线段的交集。对于两条线段,已知线段的两个端点,重合部分的两个端点肯定都在这两个线段的区间之内。所以对4个点逐一进行判断,若端点均在两个线段的区间内,也就是... -
CodeForces-1131B. Draw!(求区间交集)
2019-02-28 23:56:50题意:给你n段区间,让你求这些区间的所有交集和是多少? 分析:求区间交集: 假如min(a[i],b[i]) < max(a[i - 1],b[i - 1]) 那么continue; 现在考虑两种情况: (1)if(a[i] == b[i]) 那么我们计算a[i]... -
hdu 1006 时钟求交集
2012-10-30 21:35:21膜拜网上各种解法啊,主要就是个数学问题、、但是真心不会啊,这道题学到一些,处理时钟问题的方法吧,还有区间求交集什么的。。。 http://blog.csdn.net/lulipeng_cpp/article/details/7320710 O -
matlab求区间交集_Matlab基础(三)
2021-01-30 06:19:45目录前言假如你是大学生(一)符号表达式函数求极限泰勒展开函数求导求不定积分求定积分前言上一篇实际上是一个小插曲,向大家介绍并展示了一段简短的python小程序在实现“文件批量处理”方面的强大功用!接着上上一篇... -
如何使两个list集合合并_七十二、区间合并,插入求交集, 删除被覆盖区间
2021-01-12 14:27:20「---- Runsen」 ❞我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人... -
区间和重叠合并 python_九月,区间合并,插入,求交集,删除被覆盖区间算法...
2020-12-10 17:35:51@Author:Runsen我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。... -
如何使两个list集合合并_七十二、区间合并,插入求交集,删除求覆盖元素
2021-01-12 14:27:22「---- Runsen」❞我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。... -
输入两个闭区间,求其交集,并集和差集(C++):
2013-05-31 22:00:26输入两个闭区间,求其交集,并集和差集(C++) #includeusing namespace std; int main(){ int a,b; int c,d; cout>a>>b; cout>c>>d; if(a>b||c>d) { cout } else { if(d { cout空集" cout并集为:" cout }... -
求n个闭区间的所有交集(贪心+线段树)
2019-09-07 07:58:03思路:这是对于力扣986地一个拓展,如果问题约束到一个交区间最多只有两个大区间包含它,那么就可以先把区间预处理成像力扣986那样的两个递增区间,用双指针求交集。 对于这个问题我们也是要... -
存在多个时间区间的集合,求与集合内所有其他元素时间区间都没有交集的元素
2020-08-24 17:28:48存在多个时间区间**[开始时间,结束时间]**的集合,求与集合内所有其他元素时间区间都没有交集的元素。 图示如下: 解决方案: 保证所有其他元素的结束时间在该元素的开始时间之前,或者开始时间在该元素的结束时间...
-
各种格式测试视频(.avi.wmv.mkv.mp4.mov.rm)
-
Redis Desktop Manager_023210734.exe
-
TypeError: cleanWebpackPlugin is not a constructor 错误解决
-
scala-intellij-bin-2020.3.20.zip
-
质量保证书-源码
-
PHP动态修改PHP配置文件(通过正则替换)
-
FPGA进阶学习路线.pdf
-
网上行销原则.txt
-
MySQL 备份与恢复详解(高低版本 迁移;不同字符集 相互转换;表
-
css的各种选择器和css语法规范
-
Unity RUST 逆向安全开发
-
面试题,喝汽水问题(建议收藏)
-
如何获取TFS的任务ID状态
-
每日精选12条新闻1条微语12条简报1条心语
-
Linux查找大文件并自动删除(日志管理)
-
jquery中的not怎么用
-
NFS 实现高可用(DRBD + heartbeat)
-
MySQL 性能优化(思路拓展及实操)
-
masonry瀑布流插件, item设置transition后,layout无效
-
PHP中路由和rewrite的使用