使用分治法和中位数从未排序的数组中查找缺失的数字

Question

假设我们有一个未排序的数组，其中的数字从 0 到 n（n = 2^k - 1，k 是一个整数），除了一个。我的目标是找到丢失的号码。

我知道异或法或求和法。但是，我必须使用分而治之的策略和一些与数组的中位数有关的东西。

我的想法是求数组的中位数，然后递归的把数组分成2个数组。（一个将拥有小于或等于中位数的数字，另一个将拥有更大的数字。类似于二进制搜索）。

但是，我认为这行不通。您建议进行哪些更改？

Answer 1

您可以将数组分成 2 个数组，一个的值较小，另一个的值大于您的中位数。您可以根据第一句话的假设检查这两个数组应该有多少个元素。
其中一个数组必须比它应该的小 1。所以你可以在那里搜索。
你的退出条件将类似于数组应该包含 x 和 x 之间的所有元素（所以只有 x），但它是空的。因此 x 是缺失的元素。

Answer 2

这是另一个想法。

分而治之法

让缺失的数字 m 为 n / 2。
数出小于m的数字。
如果计数小于m
1. 那么，我们知道缺失的数字小于m。
2. 否则，缺失数大于等于m。

继续这样做，直到找到丢失的号码。

Python 实施：

def missingNumber(nums):

    lo, hi = 0, len(nums)

    while lo < hi:
        m = (lo + hi + 1) // 2
        smaller = sum(x < m for x in nums)

        if smaller < m:
            hi = m - 1
        else:
            lo = m

    return lo

使用分治法和中位数从未排序的数组中查找缺失的数字

Find the missing number from an unsorted array using divide and conquer and median numbers

arrays

median

divide-and-conquer

分而治之法

Python 实施：