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

Question

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

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

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

Answer 1

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

我们还称 k 为 B 中零的数量。

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

然后将相应的(非零)值从A[i] 分配给B[i]。然后重复这 k 次。由于 k 是常量，它不会影响时间复杂度:O(klogn) 当 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);