有沒有辦法在一個范圍內快速查找包含給定范圍內的數字？

在查詢O(log(n))較多的地方回答每個查詢，如果需要預設，在小于的時間復雜度內完成O(n^2)

所以這里有一個問題，我得到一個整數陣列，它的數字都是不同的，假設它是

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因為 from index = 0 to 2，有21, 34, 12并且有兩個數字，21, 34，在 的范圍內20 to 50。

所以另一個例子是check(2, 3, 20, 80)應該回傳，false因為那里12, 88沒有 20, 80 范圍內的數字。

我正在考慮使用 Segment Tree，因為據我所知，RMQ（范圍最小查詢）可以通過使用 Segment Tree 來解決，因此我認為 Segment Tree 也可以解決這個問題；然而，所有的"get" functionSegment Tree 都是"single"（也許不是最好的詞），所以，我想知道 Segment Tree 應該包含哪些節點。是否有任何演算法可以回答每個查詢，O(log(n))而"build" time不是O(n^2)，n陣列的大小在哪里？

注意：使用 Segment Tree 只是我自己的想法，任何其他方法都值得贊賞。

uj5u.com熱心網友回復：

這有點奇怪，但是持久的紅黑樹或任何其他自平衡樹的持久變體都可以。

甲持久資料結構允許一個（時間和空）有效地采取該結構的“快照”在不同的時間，然后稍后查詢這些快照，接收基于該結構的狀態的快照時間的結果。對于這個用例，我們想要做的特定查詢是對給定范圍內的所有包含元素進行計數（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)對查詢的要求，一種更簡單且可能更實用的方法是二維kD 樹。只需插入每個data[i]作為點(i, data[i])，然后進行范圍搜索a<=x<b, l<=y<r。這為您提供了 的查詢時間O(sqrt(n))，雖然效率不高，但更容易撰寫代碼（或查找現有代碼）。

uj5u.com熱心網友回復：

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有效的方法將花費足夠的時間建立必要的資料結構，這是不值得，除非你正在做的作業很多查詢的一個巨大的資料集。即便如此，也許上述的并行版本可能就足夠了。

uj5u.com熱心網友回復：

我對這個答案不太確定，我對它做了一些測驗，所以它可能有問題。

您可以檢查此代碼以對子陣列中的數字范圍進行二分搜索。

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

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 minFind = findMinBoundary(data, min);
    int maxFind = findMaxBoundary(data, max);
    // System.out.println(minFind   " "   maxFind);
    return (minFind != -1 || maxFind != -1);
}

// return -1: outside boundary.
static int findMinBoundary(int[] data, int boundary) {
    int start = 0;
    int end = data.length - 1;
    int ans = -1;
    if (data[0] >= boundary) {
        while (start <= end) {
            int mid = (start   end) / 2;
            if (data[mid] <= boundary) {
                start = mid   1;
            }
            else {
                ans = mid;
                end = mid - 1;
            }
        }
        if (ans == -1)
            return (data[end] >= boundary) ? end : -1;
    }
    return ans;
}

// return -1: outside boundary.
static int findMaxBoundary(int[] data, int boundary) {
    int start = 0;
    int end = data.length - 1;
    int ans = -1;
    if (data[end] <= boundary) {
        while (start <= end) {
            int mid = (start   end) / 2;
            if (data[mid] < boundary) {
                start = mid   1;
            }
            else {
                ans = mid;
                end = mid - 1;
            }
        }
        if (ans == -1)
            return (data[end] <= boundary) ? end : -1;
    }
    return ans;
}

輸出：

true
false

標籤：爪哇 数组 算法 段树

上一篇：如何減少卡爾達諾三元組演算法所花費的時間？

下一篇：查詢圖中的最短路徑演算法