- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
令 range 为两个整数的数组:start
和 end
(例如 [40, 42]
)。
有两个范围数组(已排序),我想找到计算它们交集的最佳方法(这将导致另一个范围数组):
A = [[1, 3], [7, 9], [12, 18]]
B = [[2, 3], [4,5], [6,8], [13, 14], [16, 17]]
十字路口:
[[2, 3], [7, 8], [13, 14], [16, 17]]
最佳算法是什么?
天真的方法是检查所有其他的每一个,但这显然不是最优的。
我在 VBA 中发现了一个类似的问题,要求同样的事情:Intersection of two arrays of ranges
最佳答案
由于输入数组已排序,因此计算起来应该相当简单。我假设任何一个输入数组中的范围都不会相互交叉(否则,“已排序”将是模棱两可的)。考虑每个数组中的一个范围(由“当前范围”索引 a
和 b
定义)。有几种情况(除了“完全重叠”之外的每种情况都有 A
和 B
颠倒的镜像):
没有交集:
A[a]: |------|
B[b]: |---|
因为数组是有序的,A[a]
不能与B
中的任何东西相交,所以可以跳过(增加a
)。
部分重叠(B[b]
超出A[a]
):
A[a]: |-------|
B[b]: |-------|
在这种情况下,将交集添加到输出,然后递增 a
,因为 A[a]
不能与 B
中的任何其他内容相交。
收容(可能有一致的结局):
A[a]: |------|
B[b]: |--|
再次将交集添加到输出中,这次递增 b
。请注意,进一步的轻微优化是,如果 A[a]
和 B[b]
以相同的值结束,那么您可以递增 b
同样,因为 B[b]
也不能与 A
中的任何其他内容相交。 (两端重合的情况可以归为部分重叠的情况。这种情况可以称为“严格遏制”。)
完全重叠:
A[a]: |------|
B[b]: |------|
将交集添加到输出并递增 a
和 b
(两个范围都不能与另一个数组中的任何其他内容相交)。
继续迭代上述内容,直到 a
或 b
运行到相应数组的末尾,您就完成了。
将上面的内容转化为代码应该是
微不足道的
。
编辑:为了支持最后一句话(好吧,这不是微不足道的),这是我的代码版本。由于所有情况,这有点乏味,但每个分支都非常简单。
const A = [[1, 3], [7, 9], [12, 18]];
const B = [[2, 3], [4, 5], [6, 8], [13, 14], [16, 17]];
const merged = [];
var i_a = 0,
i_b = 0;
while (i_a < A.length && i_b < B.length) {
const a = A[i_a];
const b = B[i_b];
if (a[0] < b[0]) {
// a leads b
if (a[1] >= b[1]) {
// b contained in a
merged.push([b[0], b[1]]);
i_b++;
if (a[1] === b[1]) {
// a and b end together
i_a++;
}
} else if (a[1] >= b[0]) {
// overlap
merged.push([b[0], a[1]]);
i_a++;
} else {
// no overlap
i_a++;
}
} else if (a[0] === b[0]) {
// a and b start together
if (a[1] > b[1]) {
// b contained in a
merged.push([a[0], b[1]]);
i_b++;
} else if (a[1] === b[1]) {
// full overlap
merged.push([a[0], a[1]]);
i_a++;
i_b++;
} else /* a[1] < b[1] */ {
// a contained in b
merged.push([a[0], a[1]]);
i_a++;
}
} else /* a[0] > b[0] */ {
// b leads a
if (b[1] >= a[1]) {
// containment: a in b
merged.push([a[0], b[1]]);
i_a++;
if (b[1] === a[1]) {
// a and b end together
i_b++;
}
} else if (b[1] >= a[0]) {
// overlap
merged.push([a[0], b[1]]);
i_b++
} else {
// no overlap
i_b++;
}
}
}
console.log(JSON.stringify(merged));
您要求优化算法。我相信我的非常接近最佳。它与两个数组中的范围数以线性时间运行,因为每次迭代完成至少一个范围(有时是两个)的处理。它需要常量内存加上构建结果所需的内存。
我应该注意,与 CertainPerformance 的答案(我写这篇文章时这里发布的唯一其他答案)不同,我的代码适用于任何类型的数字范围数据,而不仅仅是整数。 (如果您混合使用数字和数字的字符串表示形式,则可能需要将上面的 ===
替换为 ==
)。 CertainPerformance 的算法将范围展平为跨越范围的连续整数数组。如果整数总数为 n,则他的算法在 O(n2) 时间和 O(n) 空间内运行。 (因此,例如,如果其中一个范围是 [1, 50000],则需要存储 50,000 个数字的内存和与其平方成正比的时间。)
关于javascript - 如何相交两个范围数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49453867/
我有一个标记的个体列表(Mark 列),这些个体在河流(LocStart 和 LocEnd)范围内的不同年份(Year 列)被捕获。在河上的位置以米为单位。 我想知道一个被标记的个体是否在不同年份之间
我目前正在开发一个事件管理系统,其中数据库存储时隙,如下所示: SlotId | DateTime | Duration -------+-------------------
给定同一个圆的两个圆段:A=[a1, a2] 和 B=[b1, b2],其中: a1、a2、b1、b2 的值介于 -inf 和 +inf 之间 a1 overlap A=[ -45°, 45
试图让两个数据集相交,但我做不到。例如,在我下面的代码中,相交 mySet 和 mySet2 应该产生“1”,因为它们在它们的集合中都有一个值“1”。 var mySet = new Set(); v
给定同一个圆的两个圆段:A=[a1, a2] 和 B=[b1, b2],其中: a1、a2、b1、b2 的值介于 -inf 和 +inf 之间 a1 overlap A=[ -45°, 45
我有两个要相交的集合,并对匹配元素执行求和运算。 例如集合是(在伪代码中): col1 = { {"A", 5}, {"B", 3}, {"C", 2} } col2 = { {"B", 1}, {"
我有一个使用 -setFrameRotation 旋转的 NSView。 (这是必要的,因为 View 响应鼠标事件,如果您仅使用旋转的 NSAffineTransform 绘制 View ,则不会获
我在网上找到了这段代码,显然它对其他人有效,但对我无效?我不知道哪里错了。我做了一个简单的例子,并将我的 Range1 和 Range 2 设为 excel 中的某些单元格, 另外,我想知道是否有办法
确定直线是否与矩形相交的最有效方法是什么? 我正在寻找类似的东西: CGPoint startLine = CGPointMake(5.0f,5.0f); CGPoint endLine = CGPo
QPolygonF有与其他 QPolygonF 并集、相交和相减的方法,但我需要与 QLineF 执行相交测试。 API 中似乎缺少此功能。 我想我可以做这样的事情: if (polygon .con
所以,我尝试使用矩形在游戏中对墙壁进行碰撞,我决定尝试使用 ArrayList 来存储每面墙的矩形,然后我将整个 field 设为一面墙,并且所有我想做的是删除三堵墙,所以我正在执行 shapeLis
鉴于这两个表/集合具有不同的项目组, 我如何找到 set1 中的哪些组跨越 set2 中的多个组? 如何找到 set1 中的组不能被 set2 中的单个组覆盖? 例如对于下表,A (1,2,5) 是唯
我在 Hive 中有两个字符串数组,例如 {'value1','value2','value3'} {'value1', 'value2'} 我想合并没有重复的数组,结果: {'value1','va
谁能给我 tsql 来查找包含起始日期和截止日期的日期。 select * from empc where DateFrom >= p_todate AND DateTo = p_fromdate 关
我正在尝试从分桶列中获取子集,然后获取交集。 这将从原始表中选择其他列。 我也对系列过滤持开放态度。 下面的代码报告 col1 不存在 - 不确定这是正确的方法。 WITH ranges AS (
SELECT friend_id FROM friendships WHERE user_id = 1; Returns: +-----------+ | friend_id | +---------
似乎无法在任何地方找到这个问题的答案。 我的游戏在用户触摸屏幕时开始,手指必须停留在一条路径内,如果它触摸/与边缘相交,那么我希望它运行 [self gameover] 方法。 边缘将是一个 UIIm
我有两个 RDD,一个非常大,另一个小得多。我想用小 RDD 的键在大 RDD 中找到所有唯一的元组。 大 RDD 太大,我必须避免完全洗牌 小型 RDD 也足够大,我无法广播它。我也许可以广播它的
所以我有两个函数的代码。第一个打印一个空的 20x20 板,第二个打印中间的一个字。现在我正在尝试编写一个函数来检查输入的单词是否会与同一字母的另一个单词(如填字游戏)相交。这是前两个函数的代码(此处
我正在一个网站上进行培训,该网站要求我制作一个程序,该程序将询问两个矩形的坐标并检查矩形是否相交。然后,当我发送程序时,网站会对其进行几次测试。它要求 A 矩形的 x 最小值、x 最大值、y 最小值和
我是一名优秀的程序员,十分优秀!