如何快速找出一个区间中是否包含给定范围内的数字？

Question

这里有一个问题，给定一个整数数组，其中所有数字都是不同的，假设它为

int[] data = {21, 34, 12, 88, 54, 73};

现在我想判断一个子数组或范围是否包含在给定范围内的数中。换句话说，我想看看数组的范围是否包含在范围内的数字。例如，如果我有一个函数check（int a，int b，int l，int r），其中a和b是数组的范围，l和r是数字的范围。

因此，对于上面的数组，check（0,2,20,50）应返回true，因为从index = 0到2，有21,34,12且有两个数字 21,34 在20至50的范围内。 因此，另一个示例将是check（2,3,20,80）应返回false，因为没有任何数字在20,80的范围内。

我考虑使用线段树，因为据我所知，RMQ（区间最小查询）可以通过使用线段树解决，因此我认为线段树也适用于这个问题; 然而，所有线段树的“get”功能都是“单个”（也许不是最好的词），因此，我想知道线段树应该保存哪些节点。是否有任何算法可以在 O（log（n））内回答每个查询，而建立时间不是 O（n ^ 2），其中n是数组的大小？

注意：使用线段树只是我自己的想法，欢迎任何其他方法。

- lier wu

---

array[i] 的范围是什么？ - Abhinav Mathur

@nice_dev 两个整数，check(int a, int b, int l, int r)，我将传入两个整数，a表示左端点，b表示右端点。 - lier wu

@nice_dev，我现在明白了，那是个问题，实际上，如果我想用线段树解决这个问题，那就是我所面临的问题。这也是我提出问题的原因。我会更新问题以使其更清晰，谢谢。 - lier wu

你能同时处理所有的查询吗？这会让这个问题变得更容易。 - Matt Timmermans

...这就是为什么你要在SO上提问的原因 :) 我在被接受的答案下添加了一条评论。 - Matt Timmermans

Answer 1

这可能有点陌生，但持久化的红黑树或其他自平衡树的持久化变种都可以胜任。 持久化数据结构 可以让你以时间和空间效率高的方式，在不同的时间点“快照”结构，并在稍后查询这些快照，得到基于结构在快照时间状态的结果。对于此用例，我们想要执行的特定查询是计算给定范围内包含的所有元素的数量（如果每个节点都带有其后代数量的注释，则可以在O (log n)中执行）。

在这种情况下，您将从空结构开始，然后在时间i插入data [i]，并将快照存储为snapshot [i]。然后，check(a,b,l,r) 将被实现为return snapshot[b].countInRange(l,r) > snapshot[a].countInRange(l,r)。也就是说，如果截至时间b目标范围内有更多元素，而截至时间a目标范围内的元素较少，则必须在a和b之间添加了一些目标范围内的元素，从而满足您的条件。

如果最优地实现，则预计算需要时间O(n log n)和空间O(n)，而查询需要时间O(log n)。

---

如果您愿意放宽对查询的O(log n)要求，则一种更简单且可能更实用的方法是使用二维k-D 树。将每个data[i]插入为点(i,data[i])，然后执行a<=x<b,l<=y<r的范围搜索。这使得你的查询时间为O(sqrt(n))，虽然不如效率高，但编码（或查找现有代码）更容易。

- Sneftel

---

@miiiii 快照作为结构本身的一部分进行存储（这就是它们在空间上高效的原因）。每个快照只需要 O(1) 的平摊额外空间。 - Sneftel

谢谢回复。但是countInRange应该如何实现呢？对于每个a、b、l、r组合，它会预先计算/存储数据吗？ - miiiii

@miiiii 它的实现方式与普通的红黑树一样，通过递归访问与范围重叠的节点来实现。它没有为任何特定的输入集预先计算。 - Sneftel

红黑树是二叉搜索树吗？二叉搜索树不允许重复，是一棵有序的树。那么它如何对这种情况有用呢？如果我偏离了轨道，请纠正我。到目前为止，您一直是一个好的解释者:) 我很感激。 - miiiii

由于OP在评论中指出您已经提前拥有了所有的查询，因此您不需要使用持久化树。将查询按l和r排序后制作两个列表。然后按顺序将点插入普通的顺序统计树中。当您穿过一个查询l时，计算范围内的值的数量。当您穿过一个查询r时，计算范围内的值的数量并减去先前的计数。如果答案>0，则满足查询。 - Matt Timmermans

Answer 2

O(N) 很容易：

public static boolean check(int[] data, int a, int b, int l, int r) {
    return Arrays.stream(data, a, b + 1).anyMatch(n -> n >= l && n <= r);
}

我怀疑除非你在巨大的数据集上进行了很多查找，否则任何更高效的大O方法都会花费足够的时间来构建所需的数据结构，这并不值得努力。即使如此，也许上述方法的并行版本可能已经足够好了。

- Shawn

---

谢谢，但我需要很多查找... 因此，如果需要数据结构来回答查询（在log(n)内），我希望能够以小于O(n^2)的时间复杂度构建它。 - lier wu

Answer 3

更新：

public static void main(String[] args) {
    int[] data = {21, 34, 12, 88, 54, 73, 99, 100};
    List<Integer> dataList = Arrays.stream(data).boxed().collect(Collectors.toList());
    System.out.println(searchRange(0, 2, 20, 50, data));
    System.out.println(searchRange(2, 3, 20, 80, data));
    System.out.println(searchRange(0, 2, 20, 22, data));    

public static boolean searchRange(int from, int to, int min, int max, int[] data) {
    // slice array
    data = Arrays.copyOfRange(data, from, to + 1);
    Arrays.sort(data);
    // System.out.println(Arrays.toString(data));
    int index = findInBoundaries(data, min, max);
    // System.out.println(index);
    return index != -1;
}

// return -1: no elements found.
static int findInBoundaries(int[] data, int min, int max) {
    int start = 0;
    int end = data.length - 1;
    int ans = -1;
    while (start <= end) {
        int mid = (start + end) / 2;
        // Break if found 
        if (data[mid] >= min && data[mid] <= max) {
            ans = mid;
            break;
        } 
        // Right move if element <= max
        else if (data[mid] <= max) {
            start = mid + 1;
        }
        // Left move
        else {
            end = mid - 1;
        }
    }
    return ans;
}

输出

true
false
true

这段代码已经进行了多次测试。与我第一个回答中独立命中最小值和最大值边界的方法不同，这个方法是通过确定目标元素的范围来判断子数组是否包含符合条件的数字。

解释：

为了简化问题，我将其定义为如果子数组中的任何数字在给定范围内，并且方法的时间复杂度应小于O(n^2)。

一旦数组排序完成，就可以使用二分搜索来解决。解决方案从中间元素开始（int mid = (start + end) / 2），在给定范围内搜索一个数字。当元素满足范围要求时，循环终止。如果它小于（或小于等于）最大值，则搜索右侧（较大）元素；否则，搜索左侧（较小）元素。在这种情况下，最大循环次数将为O(log n)，其中n是数组的大小。

示例：

我修改了代码以通过添加计数器来比较解决方案与普通循环的效率。在某些情况下，普通循环需要遍历整个数组。 普通解决方案的排序并不是非常重要，所以我没有进行排序。

// return -1: no elements found.
static void findBoundaryCompareMethods(int[] data, int min, int max) {
    int start = 0;
    int end = data.length - 1;
    int ans = -1;
    int count = 0;
    while (start <= end) {
        int mid = (start + end) / 2;
        count++;
        // Right move to find element > max 
        if (data[mid] >= min && data[mid] <= max) {
            ans = mid;
            break;
        } 
        else if (data[mid] <= max) {
            start = mid + 1;
        }
        // Left move
        else {
            end = mid - 1;
        }
    }
    System.out.println("Method 1 Find: " + ans);
    System.out.println("Method 1 Count: " + count);
    ans = -1;
    count = 0;
    for (int i = 0; i < data.length; i++) {
        count++;
        if (data[i] >= min && data[i] <= max) {
            ans = i;
            break;
        }
    }
    System.out.println("Method 2 Find: " + ans);
    System.out.println("Method 2 Count: " + count);
}

测试输出如下。方法1是答案解决方案，方法2是正常解决方案。 输出

Array: [12, 21, 34]
Min: 20 Max: 50
Method 1 Find: 1
Method 1 Count: 1
Method 2 Find: 1
Method 2 Count: 2

Array: [12, 88]
Min: 20 Max: 80
Method 1 Find: -1
Method 1 Count: 2
Method 2 Find: -1
Method 2 Count: 2

Array: [12, 21, 34]
Min: 20 Max: 22
Method 1 Find: 1
Method 1 Count: 1
Method 2 Find: 1
Method 2 Count: 2

Array: [12, 21, 34, 54, 73, 88, 99, 100]
Min: 70 Max: 73
Method 1 Find: 4
Method 1 Count: 3
Method 2 Find: 4
Method 2 Count: 5

- Wing Kui Tsoi

---

System.out.println(searchRange(0, 2, 20, 22, data)); 返回false，但期望为true。使用min和max决策并不能总是有帮助。 - nice_dev

您的代码针对每个查询都进行排序，导致查询时间为O(n log n)。没有必要这样做。直接线性扫描会更快（O(n)）。 - Sneftel

@WingKuiTsoi 我现在理解你的方法了，但是对于每个子数组进行排序会很耗时间。最坏情况下时间复杂度将为O(N * n * log(n))，其中N是要回答的查询数，n是整个数组的大小。因此，如果函数的范围是整个数组作为子数组，它的性质是二次的。这种情况下，每个查询的简单O(n)遍历将更具有性能优势。 - nice_dev

对于每个查询，运行排序例程需要O(n log n)的时间。因此，如果有N个查询，则总复杂度为O(N * n log n)。如果您只是线性搜索每个查询的数组，则仅需要O(N * n)的时间。 - Sneftel

排序需要O(n log n)的时间，而二分查找需要O(log n)的时间，因此每个查询的总时间为O(n log n + log n) = O(n log n)。这是基本的计算机科学知识。 - Sneftel