找到带有O(1)空格和O(n)时间的重复数字

Question

我在leetcode中解决了一个问题

给定包含n + 1个整数的数组nums,其中每个整数在1和n之间(包括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

你的问题实际上很难回答.通常在处理复杂性时,会假设机器模型.标准模型假设当输入大小为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从数组的总xor中进行xor,并找到重复的值.

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)位).