有没有办法快速找到一个范围内包含给定范围内的数字？

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) 应该 return true 因为从 index = 0 to 2 开始，有 21, 34, 12 并且有两个数字，21, 34，在 20 to 50.

范围内

所以另一个例子是 check(2, 3, 20, 80) 应该 return false 因为那里 12, 88 没有数字在 20、80 范围内。

我正在考虑使用Segment Tree，因为据我所知，RMQ(range minimum query)可以使用Segment Tree来解决，所以我认为Segment Tree也可以解决这个问题；然而，线段树的所有"get" function都是"single"（也许不是最好的词），所以，我想知道线段树应该包含哪些节点。有什么算法可以回答 O(log(n)) 中的每个查询，而 "build" time 不是 O(n^2)，其中 n 是数组的大小？

注意：使用线段树只是我自己的想法，任何其他方法都值得赞赏。

Answer 1

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);
}

我怀疑任何更高效的 big-O 方法都会花费足够的时间来构建所需的数据结构，除非您在 lot 上进行查找，否则不值得付出努力一个巨大的数据集。即便如此，也许上述的并行版本就足够了。

Answer 2

更新：

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);
}

测试输出如下。方法一为正解，方法二为正解

输出

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

Answer 3

这有点奇特，但是持久性红黑树或任何其他自平衡树的持久性变体都可以。

A persistent data structure 允许（时间-和 space-）在不同时间有效地拍摄结构的“快照”，然后稍后查询这些快照，接收基于结构的结果截至快照时间的状态。对于这个用例，我们想要做的特定查询是计算给定范围内所有包含的元素（如果每个节点都用其后代的数量注释，则可以在 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) 和 space O(n)，查询将花费时间 O(log n).

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

有没有办法快速找到一个范围内包含给定范围内的数字？

Is there a way to quickly find in a range contains a number that is in a given range?

java

arrays

algorithm

segment-tree