如何在一组连续范围中查找给定数字的范围

Question

如何在一组连续范围中查找给定数字的范围

7

简单来说，我想做的是：

我有一组连续的Range对象（不重叠，它们之间没有间隙），每个对象都包含一个start和一个end整数，以及对另一个对象obj的引用。这些范围的大小不固定（第一个可能是1-49，第二个可能是50-221等）。这个集合可能会变得非常大。

我希望找到一种方法，在不必遍历整个集合检查每个范围是否包含该数字的情况下查找包含给定数字的范围（更具体地说，是它所引用的对象）。这些查找将经常进行，因此速度/性能至关重要。

有人知道一个算法/方程可以帮助我吗？我用Java编写。如果需要，我可以提供更多详细信息，但我想尽量简单明了。

谢谢。

- IgnisFatuus

1

范围可以重叠吗？ - azurefrog

对于我的目的，它们不会重叠。 - IgnisFatuus

如果这样做有所不同，那么范围之间也永远不会有间隙。即 (ranges[i].end + 1 == ranges[i +1].start) 总是成立的……虽然我没有使用数组，但你可以理解我的意思。 - IgnisFatuus

3个回答

1

假设您的查找是最重要的，并且可以节省O（N）的内存和大约O（N ^ 2）的预处理时间，则算法如下：

引入一个类ObjectsInRange，其中包含：范围开始（int startOfRange）和对象集合（Set<Object> objects）
引入一个ArrayList<ObjectsInRange> oir，其中包含按startOfRange排序的ObjectsInRange
对于每个Range r，确保存在ObjectsInRange（我们称之为a和b），使得a.startOfRange = r.start和b.startOfRange = b.end。然后，对于a之间的所有ObjectsInRange x，并且直到（但不包括）b，将r.obj添加到它们的x.objects集合中

然后进行查找：

对于整数x，找到这样的i，使得oir[i].startOfRange <= x且oir[i+1].startOfRange > x
注意：可以在O(log N)时间内通过二分法找到i！
你的对象是oir[i].objects

- kzagar

感谢kzagar的回答！我选择azurefrog的解决方案以便于实施。很想给您点赞以示好的回答，但目前系统不允许我这样做... - IgnisFatuus

是的，azurefrog的实现更容易。但是我的解决方案也适用于范围重叠的情况（虽然在您的情况中不是必需的）。 - kzagar

0

如果集合有序，则可以实现二分查找来在O(log(n))时间内找到正确的范围。对于非常大的集合，它不像哈希那样高效，但如果您有不到1000个范围，它可能会更快（因为更简单）。

- Ypnypn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- azurefrog · Accepted Answer

如果您想使用TreeMap，其中键是范围底部，值是Range对象，则需要使用该方法来识别正确的范围：floorEntry()方法可以非常快速地获取最接近（小于或等于）键的Range，应该包含键，如下所示：

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

由于树总是按照底部范围边界的自然顺序排序，您所有的搜索最坏情况下都将是O(log(n))。

当您的键完全超出范围时（例如，当键超出地图的末尾时，它会返回地图中的最后一个Range），您需要添加一些合理性检查，但这应该可以给您提供如何继续的想法。