在 O(log(n)) 时间内找到数组中缺失的数字

Question

我得到了两个数组 A 和 B，其中 A 完全由正整数填充，而 B 是 A，其中一些常量元素变成了零。我还得到了一个任意函数，它接受一个数组并给出 O(1) 中从 a 到 b 的数组总和，其中 a 和 b 是数组中的索引。

我应该设计一种算法，在 O(log(n)) 时间内将数组 B 转换为数组 A，但我很难理解这是如何实现的。

我想出了一个复杂度为 O(n) 的解决方案，我只是将 A 的索引与 B 的索引进行比较。如果它们相同，我将继续循环，如果它们不同，我将 B[i] 的值更新为 A[i]。我看不到改善这一点的方法，尤其是在数组未排序的情况下。

Answer 1

二进制搜索零元素。（提示：如果 sum(A, lo, hi) ≠ sum(B, lo, hi) 则范围至少包含一个零元素。如果你有这样一个范围，你可以将它分成两半：如果前半部分包含零元素，则继续前半部分，否则继续下半部分。当你到达一个元素范围时停止。

Answer 2

让我们调用给定的函数sum。如前所述，您可以将其称为 sum(array, i, j)，它会 return array[i] + ... + array[j-1] 的总和。我假设该范围不包括 j 本身的索引，但如果包含它，推理是相同的。

我们也称 k 为 B.

中零的个数

现在您可以使用二进制搜索找到 B 中最左边的 0，方法是将 sum(A, 0, i) 与 sum(B, 0, i) 进行比较，同时改变 [=42] =]i 按照二分查找法。然后，当找到那些总和不相等的最低索引时，您就会知道 B[i] 为零，并且在 O(logn) 时间。

于是将A[i]对应的（非零）值赋值给B[i]。然后重复此 k 次。由于k是常量，所以不影响时间复杂度：O(klogn)仍然是O(logn) 当 k 是常量时，例如 2.

这是 JavaScript 中的一个实现，带有示例输入，k=2。

// Implementation of the hidden function, which (contrary to this implementation)
// should run in constant time
function sum(arr, i, j) {
    result = 0;
    while (i < j) {
        result += arr[i++];
    }
    return result;
}

// example
let a = [3,2,6,7,1,9,8,5];
let b = [3,2,0,7,1,9,0,5];
let n = a.length;
let k = 2;

for (let times = 0; times < k; times++) {
    // Apply binary search
    let low = 0;
    let high = n;
    while (low < high) {
        let mid = (low + high + 1) >> 1;
        if (sum(a, 0, mid) == sum(b, 0, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    // Found index where zero is at:
    b[low] = a[low];
}

console.log(b);

当k未知时

...那么它不是常数，而是变量。时间复杂度则变为 O((k+1)logn)，即 O(klogn)，循环必须一直进行下去，直到搜索不再找到零（在 (k+1)^th 迭代）：

// Implementation of the hidden function, which (contrary to this implementation)
// should run in constant time
function sum(arr, i, j) {
    result = 0;
    while (i < j) {
        result += arr[i++];
    }
    return result;
}

// example
let a = [3,2,6,7,1,9,8,5];
let b = [3,2,0,7,1,9,0,5];
let n = a.length;
// no definition of k here

while (true) {
    let low = 0;
    let high = n;
    while (low < high) {
        let mid = (low + high + 1) >> 1;
        if (sum(a, 0, mid) == sum(b, 0, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (low >= n) break; // no zero found
    // Found index where zero is at:
    b[low] = a[low];
}
console.log(b);

在 O(log(n)) 时间内找到数组中缺失的数字

Find missing numbers in array in O(log(n)) time

arrays

algorithm

performance

complexity-theory

当k未知时