python - 如何找到输入中不存在的 4 字节数字？

Question

我有这样的任务，实际上不知道如何开始。在输入中，我有一个巨大的 4 字节正数数组。数字可以重复。我知道其中一个数字不包含在输入数组中。我如何使用最少的资源找到这个数字？

Answer 1

最简单的代码可能是(伪代码):

function find_missing(input)
    sort!(input)   # in-place sort, should take most of the time
    val = 0
    for d in input    # go over sorted input
        if d == val
            val += 1
        end
        if d > val
            break
        end
    end
    return val
end

上述函数应返回缺失值或零(以防因整数回绕而没有缺失值)。如果缺失值为零，则有点困惑，但修复很简单，留给读者。

注意:这不是最快的方法。更快的方法将使用多次传递将输入拆分为子集，并使用最大可用内存分析这些子集。