algorithm - 确定一个值是否在多个范围内的有效方法

Question

想象一下，我有一个值：x和一个值范围：（y to z假设y < z）。确定是否x属于范围y to z很简单：

if(x >= y && x <=z)
   true
else
   false

现在想象一下，我再次拥有我的 value x，但我有一个范围列表：[ y1 to z1, y2 to z2, ...]。

请注意，列表中的元素之间没有约束。范围可以重叠。一个范围可以完全落在另一个范围内。等等。

我想回答这个问题是否x属于这些范围中的任何一个范围？. 当然，我可以使用上述方法遍历列表并检查每个范围，一次一个。但我想知道我是否可以做任何优化。

理想情况下，我希望可能有一个恒定的时间解决方案，也许通过以某种方式对范围进行排序并做一些聪明的事情。但它只是没有来找我。

如果没有恒定时间解决方案，我会接受一个提出优化的答案，并解释为什么这是O(n)可实现的最佳时间。或者，如果列表中的迭代确实是你能得到的最好的，我也会接受解释为什么会这样的答案。

请注意，我不需要找到所有属于的范围x。我只需要知道是真是假——至少x在其中一个范围内。

标签： algorithmoptimization

Answer 1

如果您只需要知道查询值是否在某个范围内，并且不需要恢复最小的封闭范围，那么从排序范围列表构建的排序映射就足够了。构建地图将是O(nlogn)和查询一个点将是O(logn)。

我们首先对每个范围的开始和结束进行排序，跟踪类型，以便我们可以通过在结束值之前排序开始值来打破平局。然后我们遍历排序列表，当我们遇到一个平衡的结束值时，将一个范围添加到地图中。

下面是一些 Java 代码来说明：

static TreeMap<Integer, Integer> build(int[][] intervals)
{
    List<End> ends = new ArrayList<>();
    for(int[] i: intervals)
    {
        ends.add(new End(i[0], Type.START));
        ends.add(new End(i[1], Type.END));
    }
    ends.sort((a, b) -> End.compare(a, b));

    int count = 0;
    End start = null;
    TreeMap<Integer, Integer> imap = new TreeMap<>();
    for(End end : ends)
    {
        if(end.type == Type.START)
        {
            if(count++ == 0) start = end;           
        }
        else
        {
            if(--count == 0) imap.put(start.pos, end.pos);
        }
    }
    return imap;
}

实用程序类：

static enum Type {START, END}

static class End
{
    int pos;
    Type type;
    
    public End(int pos, Type type)
    {
        this.pos = pos;
        this.type = type;
    }
    
    public static int compare(End a, End b)
    {
        int c = Integer.compare(a.pos, b.pos);
        if(c == 0) c = a.type.compareTo(b.type);
        return c;
    }
}

查找就是在映射中找到小于或等于查询的最大键并检查关联值是否大于查询值的简单问题。

static boolean lookup(TreeMap<Integer, Integer> map, int v)
{
    Integer k = map.floorKey(v);
    if(k != null) 
        return (v < map.get(k));
    return false;
}

测试：

int[][] is = {{1,4}, {4,8}, {10, 12}, {9,14}};
TreeMap<Integer, Integer> imap = build(is);     

System.out.printf("Map: %s%n%n", imap);     

for(int i=is[0][0]-1;i<is[is.length-1][1]+1; i++)
    System.out.println(i + " " + lookup(imap, i));

输出：

Map: {1=8, 9=14}

0 false
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 false
9 true
10 true
11 true
12 true
13 true
14 false