python - 查找数组中缺失的元素

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]))  

我没有得到我应该在函数中返回什么，它应该是 a[l]、a[r] 吗？

我正在了解函数内部的逻辑应该如何:如果两个数组的中间值匹配，则意味着 b 直到中点与 a 相同，因此缺少的元素必须在 mid 的右侧.

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

Answer 1

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(日志(n)日志(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)日志(K))。对于大多数情况，这应该足够好了。 :-)