代码之家 › 专栏 › 技术社区 › mourinho

查找数组中缺少的元素

binary-search data-structures algorithm python

mourinho · 技术社区 · 8 年前

我有一个有趣的问题,给定两个排序数组:

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

我得到了函数内部的逻辑应该是什么:如果两个数组的中值匹配,这意味着,直到中点与a相同为止,b,因此缺少的元素必须在mid的右边。

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

3 回复 | 直到 8 年前

btilly 8 年前

的要点 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(对数(n)对数(K)) . 进一步分析,这种说法是错误的。如果 K = log(n) 以及 log(n) 运行长度 sqrt(n) 可以点击搜索的所有选项,然后您就可以获得运行时间 O(对数(n)^2) 而不是 O(log(n)log(log(n))) .

但如果最多 log(K) 元素的重复次数超过 K 次,那么你的运行时间 O(对数(n)对数(K)) . 对于大多数情况,这应该足够好了。:-)

btilly 8 年前

这个问题的原理很简单,细节很难。

您已安排好该阵列 a 是长的那个。很好,这简化了生活。现在需要返回 一 在第一个位置 一 与的值不同 b .

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

不同的值是最后一个(即在只有数组的位置 一 具有值。
不同的值是第一个。(在这种情况下,二进制搜索算法很容易出错。
有一个运行相同。那就是 a = [1, 1, 2, 2, 2, 2, 3] 虽然 b = [1, 2, 2, 2, 2, 3] -当你在中间着陆时,价值匹配的事实可能会误导你!

祝你好运

Magua 8 年前

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

这将导致它在上次检测到不匹配时返回。