查找数组中缺失的元素

Question

我有一个有趣的问题，给定两个排序数组：

a 有 n 个元素，b 有 n-1 个元素。

b 具有 a 的所有元素，但缺少一个元素。

如何在 O(log n) 时间内找到该元素？

我试过这个代码：

def lostElements2(a, b):
    if len(a)<len(b):
        a, b = b, a

    l, r = 0, len(a)-1

    while l<r:
        m = l + (r-l)//2

        if a[m]==b[m]:
            l = m+1
        else:
            r = m - 1

    return a[r]


print(lostElements2([-1,0,4,5,7,9], [-1,0,4,5,9]))

我没有得到函数中应该 return 的内容，应该是 a[l]、a[r] 吗？

我明白了函数内部的逻辑应该是这样的：如果两个数组的中间值匹配，则意味着 b 直到中点与 a 相同，因此缺少的元素必须在右边中期

但我无法创建最终解决方案，循环应该何时停止以及应该 return 编辑什么？它如何保证 a[l] 或 a[r] 确实是缺失的元素？

Answer 1

您的代码没有处理缺少的元素是索引 m 本身的情况。您后面的 if/else 子句将始终移动缺失元素所在的边界以不包括 m.

您可以通过增加一项检查来解决此问题：

if a[m]==b[m]:
    l = m+1
elif m==0 or a[m-1]==b[m-1]:
    return a[m]
else:
    r = m - 1

另一种方法是存储 m 的最后一个值：

last_m = 0
...
else:
    last_m = m
    r = m - 1
...
return a[last_m]

这会导致它 return 上次检测到不匹配。

Answer 2

这道题原理简单，细节难。

你已经安排好数组a是较长的一个。很好，这简化了生活。现在你需要 return 在 a 的值与 b 的值不同的第一个位置 a 的值。

现在您需要确保处理以下边缘情况。

不同的值是最后一个（即在只有数组 a 有值的位置。
不同的值是第一个。（对于这种情况，二进制搜索算法很容易搞砸。
有一个运行一样。即 a = [1, 1, 2, 2, 2, 2, 3] 而 b = [1, 2, 2, 2, 2, 3] - 当您落在中间时，值匹配的事实可能会误导您！

祝你好运！

Answer 3

l和r的要点应该是l始终是列表相等的位置，而r始终是列表不同的位置. IE。 a[l]==b[l] 和 a[r]!=b[r]

代码中唯一的错误是将 r 更新为 m-1 而不是 m。如果我们知道 a[m]!=b[m]，我们就可以安全地设置 r=m。但是将其设置为 m-1 有获得 a[r]==b[r] 的风险，这会破坏算法。

def lostElements2(a, b):
    if len(a) < len(b):
        a, b = b, a
    if a[0] != b[0]:
        return a[0]

    l, r = 0, len(a)-1
    while l < r:
        m = l + (r-l)//2
        if a[m] == b[m]:
            l = m+1
        else:
            r = m # The only change
    return a[r]

（正如@btilly 指出的那样，如果我们允许重复值，此算法将失败。）

编辑自@btilly

为了修复该潜在缺陷，如果值相等，我们将搜索具有相同值的范围。为此，我们以 1、2、4、8 等大小的步长向前走，直到值切换，然后进行二分查找。同样向后走。现在寻找每条边的差异。

该搜索所需的工作量为 O(log(k))，其中 k 是重复值的长度。所以我们现在用搜索替换 O(log(n)) 查找。如果该搜索的长度有上限 K，则总时间为运行。 O(log(n)log(K))。这使得最坏情况运行时间 O(log(n)^2)。如果K接近sqrt(n)，很容易实际命中那个最坏的情况。

我在评论中声称，如果最多 K 个元素重复超过 K 次，则运行次为 O(log(n)log(K))。进一步分析，这种说法是错误的。如果 K = log(n) 和长度 sqrt(n) 的 log(n) 运行被放置以命中搜索的所有选择，那么你得到运行时间 O(log(n)^2) 而不是 O(log(n)log(log(n))).

但是，如果最多 log(K) 个元素重复超过 K 次，那么您确实会得到运行次 O(log(n)log(K))。对于大多数情况，这应该足够好了。 :-)

查找数组中缺失的元素

Finding Missing Element in an Array

python

algorithm

binary-search

data-structures