查找数字范围交点

只是一个伪代码猜测：

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest)
{
  Set<Range> results;
  foreach (rangeToTest in setofRangesToTest)
  do
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range
    results.add(rangeToTest);
  done
  return results;
}

我会制作一个 Range 类并给它一个方法 boolean intersects（Range） 。然后你可以做一个

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) }

或者，为了清楚起见，如果您使用一些 Java 8 风格的函数式编程：

rangeset.stream().filter(range::intersects).collect(Collectors.toSet())

交叉点本身是这样的

this.start <= other.end && this.end >= other.start

这在很大程度上取决于您的范围。范围可以很大或很小，可以是聚类的，也可以是非聚类的。如果你有大的聚簇范围（想想“所有可以被 2 整除的正 32 位整数”），那么使用 Range（lower， upper） 的简单方法将不会成功。

我想我可以说以下几点： 如果范围很小（聚类与否在这里无关紧要），请考虑位向量。这些小动物在并集、交集和隶属度测试方面速度极快，尽管对所有元素的迭代可能需要一段时间，具体取决于大小。此外，因为它们只对每个元素使用一个比特，所以它们非常小，除非你向它们投掷很大的范围。

如果你有更少、更大的范围，那么其他人描述的类范围就足够了。这个类具有下层和上层属集（a，b）基本上是b.upper <a.lower或a.upper >b.lower。对于单个范围和复合范围，可以以恒定时间实现并集和交集，时间随着子范围的数量而增长（因此您不希望有太多的小范围）

如果你有一个很大的空间，你的数字可以在那里，并且范围分布在一个令人讨厌的混乱中，你应该看看二元决策图（BDD）。这些漂亮的图表有两个终端节点，True 和 False 以及每个输入位的决策节点。一个决策节点有一个它所查看的位和两个跟随的图节点——一个用于“位等于一”，一个用于“位为零”。给定这些条件，您可以在狭小的空间内对大范围进行编码。任意大数的所有正整数都可以在图中的 3 个节点中编码——基本上是最低有效位的单个决策节点，在 1 上为 False，在 0 上为 True。

交集和并集是相当优雅的递归算法，例如，交集基本上在每个BDD中取两个对应的节点，遍历1条边，直到弹出一些结果并检查：如果其中一个结果是False-Terminal，则在结果BDD中创建一个指向False-terminal的1分支。如果两者都是 True-Terminal，则在结果 BDD 中创建一个指向 True-terminal 的 1 分支。如果是其他东西，请在结果 BDD 中为这个 something-else 创建一个 1 分支。在那之后，一些最小化开始（如果节点的 0- 和 1 分支转到相同的 BDD / 终端，请将其删除并将传入的转换拉到目标），您就是黄金。我们甚至走得更远，我们致力于模拟 BDD 上整数集的相加，以增强值预测以优化条件。

这些注意事项意味着您的运算受数字范围内的位数（即 log_2（MAX_NUMBER））的限制。试想一下，你可以在几乎恒定的时间内与任意的 64 位整数集相交。

例如，更多信息可以在维基百科和参考论文中获取。

此外，如果误报是可以忍受的，并且您只需要进行存在性检查，则可以查看 Bloom 过滤器。布隆过滤器使用哈希向量来检查元素是否包含在表示的集合中。交集和并集是恒定时间。这里的主要问题是，如果你把布隆过滤器填满太多，你会得到一个越来越大的误报率。 例如，信息再次在维基百科中。

呵呵，集合表示是一个有趣的领域。:)

在 python 中

class nrange(object):
    def __init__(self, lower = None, upper = None):
        self.lower = lower
        self.upper = upper
    def intersection(self, aRange):
        if self.upper < aRange.lower or aRange.upper < self.lower:
            return None
        else:
            return nrange(max(self.lower,aRange.lower), \
                          min(self.upper,aRange.upper))

如果您使用的是 Java Commons，Lang Range 有一个 overlapsRange（Range range） 方法。