我正在用 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) 时间。
谁能帮我理解为什么?
最佳答案
你的问题其实很难回答。通常在处理复杂性时,有一个假定的机器模型。 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) 位).
关于python - 找到具有 O(1) 空间和 O(n) 时间的重复数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46221289/