计算连续整数序列的交集？

Question

在JavaScript中计算连续整数序列交集的正确方法是什么？

例如 A = (1...10) 和 B = (7...20) 和 C = (3..5) — 结果我想知道 A 与 B 相交，但 B 不与 C 相交。

有什么建议吗？

Answer 1

var intersect = function(a, b) {
    // Assume a & b are sorted

  var c = []

  for(var i = 0; i < a.length; i++) {
        for(var j = 0; j < b.length; j++) {
        if(a[i] == b[j]) {
          c.push(a[i]);
        }
      }
    }
    return c;
  }

A = []
B = []

A.push(1, 3, 5, 2, 4, 7)
B.push(2,4,8,10,7,5,1)
A.sort()
B.sort()

alert(intersect(A,B))

Answer 2

我只能告诉你，我只想知道它们是否相交。

is_intersecting = (minA <= maxB && maxA >= minB);

根据评论，您可以用 a.start 代替 minA，用 a.end 代替 maxA，然后继续。将其包装在一个函数中可能更好。

Answer 3

使用 class 和 returns 一个新范围对象的方法（如果有一个结果）。此解决方案适用于任何浮动或间隙。

function Range(lower, upper) {
    this.lower = lower;
    this.upper = upper;
}

Range.prototype.intersection = function (r) {
    var i = new Range(Math.max(this.lower, r.lower), Math.min(this.upper, r.upper));
    return i.lower <= i.upper ? i : undefined;
};

var a = new Range(1, 10), //   1 2 3 4 5 6 7 8 9 10
    b = new Range(7, 20), //               7 8 9 10 11 12 13 14 15 16 17 18 19 20
    c = new Range(3, 5),  //       3 4 5
    d = new Range(0, 1);  // 0 1

function print(o) {
    document.write('<pre>' + JSON.stringify(o, 0, 4) + '</pre>');
}

print(a.intersection(b)); // { lower: 7, upper: 10 }
print(a.intersection(c)); // { lower: 3, upper: 5 }
print(a.intersection(d)); // { lower: 1, upper: 1 }
print(b.intersection(c)); // undefined
print(b.intersection(d)); // undefined
print(c.intersection(d)); // undefined

Answer 4

假设 A、B 和 C 是数组，那么您可以 assemble 一个具有边界值的对象，如下所示：

bounds_a = {
    start: Math.min.apply(null, A),
    end: Math.max.apply(null, A),

}

你甚至可以制作一个 class 来帮助：

var Bounds = function(src){
    this.min = Math.min.apply(null, src)
    this.max = Math.max.apply(null, src)
    this.size = Math.abs(max - min + 1) //+1 since we're dealing with integers and need to account for the lowest value
}

Bounds.prototype.intersects = function(target){
    rangeMin = Math.min(this.min, target.min)
    rangeMax = Math.max(this.max, target.max)

    range = Math.abs(rangeMax - rangeMin)
    width = this.size + target.size

    return range < width
}

可以在此处找到对重叠逻辑的更好解释 - What's the most efficient way to test two integer ranges for overlap?

测试这个：

var A = <array 1...10>
var B = <array 7...20>
var C = <array 3...5>

var a = new Bounds(A) //min: 1, max: 10, size: 10
var b = new Bounds(B) //min: 7, max: 20, size: 14
var c = new Bounds(C) //min: 3, max: 5, size: 3

a.intersects(b) //true
b.intersects(c) //false
a.intersects(c) //true

计算连续整数序列的交集？

Calculate intersection of continuous integer sequences?

javascript

numerical-methods