python - 找到具有 O(1) 空间和 O(n) 时间的重复数字

Question

我正在用 leetcode 解决一道题

给定一个包含 n + 1 个整数的数组 nums，其中每个整数介于 1 和 n(含)之间，证明至少必须存在一个重复数字。假设只有一个重复数，以O(n)时间和O(1)空间复杂度找到重复数

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor=0
        for num in nums:
            newx=xor^(2**num)
            if newx<xor:
                return num
            else:
                xor=newx

我接受了解决方案，但我被告知它既不是 O(1) 空间也不是 O(n) 时间。

谁能帮我理解为什么？

Answer 1

你的问题其实很难回答。通常在处理复杂性时，有一个假定的机器模型。 A standard model假设当输入的大小为 n 时，内存位置的大小为 log(n) 位，并且对大小为 log(n) 位的数字的算术运算为 O(1)。

在此模型中，您的代码不是空间 O(1) 和时间 O(n)。您的 xor 值有 n 位，这不适合常量内存位置(它实际上需要 n/log(n) 个内存位置。同样，它不是 O(n) 时间，因为算术运算是在大于 log(n) 位的数字上进行的。

要在 O(1) 空间和 O(n) 时间内解决您的问题，您必须确保您的值不会变得太大。一种方法是对数组中的所有数字进行异或运算，然后您将得到 1^2^3...^n ^ d，其中 d 是重复项。因此，您可以从数组的总异或中对 1^2^3^..^n 进行异或，并找到重复值。

def find_duplicate(ns):
    r = 0
    for i, n in enumerate(ns):
        r ^= i ^ n
    return r

print find_duplicate([1, 3, 2, 4, 5, 4, 6])

这是 O(1) 空间和 O(n) 时间，因为 r 使用的位数永远不会超过 n 使用的位数(即，大约 ln(n) 位).