在数组中查找缺失元素

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相同，因此缺失的元素必定在中间点右侧。

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

- mourinho

---

元素指的是数字？字符串？列表？ - Mr. T

@MrT 所有元素都是数字 - mourinho

为什么不用 sum(a) - sum(b)？ - Mr. T

@MrT 那将是 O(N) 复杂度，即使集合差也是 O(N) 复杂度。 - mourinho

Answer 1

这个问题的原理很简单，但细节却很难。你已经安排好数组a是较长的那一个，很好，这简化了问题。现在你需要返回a的值，该值为第一个与b的值不同的位置上的值。现在你需要确保处理以下几种边界情况。

1. 不同的值是最后一个（即仅a数组有值的位置）。
2. 不同的值是第一个（二分搜索算法很容易出错）。
3. 存在相同的一段，比如a = [1, 1, 2, 2, 2, 2, 3]而b = [1, 2, 2, 2, 2, 3]-当你落在中间时，值匹配的事实可能会误导你！

祝你好运！

- btilly

Answer 2

l和r的目的是使l始终是列表相等的位置，而r始终是它们不同的位置。也就是说，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））的运行时间。 这对于大多数情况应该足够好了。 :-)

- kuppern87

---

不需要while循环。只需搜索以找到当前值的边缘。结果是O(log(n)^2)的最坏情况算法。如果您有长度为O(sqrt(n))的O(sqrt(n))运行，则实际上会达到最坏情况的性能。并且如果大多数k次重复具有超过k个元素的运行，则该算法将是O(log(n)*log(k))。对于大多数常见情况，这实际上是一个O(log(n))算法。 - btilly

@btilly 谢谢，我已经删除了这个声明，也许您可以将您的分析作为编辑添加进去？ - kuppern87

完成。请审核。 - btilly

Answer 3

你的代码没有处理缺失元素是索引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]

这将导致它返回最后一次检测到不匹配的时间。

- Magua