找到O（1）的空间和O（n）的时间

鉴于包含n + 1点的整数，其中每个整数是1和n之间的阵列NUMS（包括重复的数），证明至少有一个重复号码必须存在。假设只存在一个重复的号码，找到重复一个在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）时间。

任何人都可以请帮我理解为什么？

来源

2017-09-14 Bhanu sri

这可能是[在O（n）和恒定空间中查找重复]（https://stackoverflow.com/questions/9072600/find-repeating-in-on-and-constant-space）和/或[如何找到算法的时间复杂度]（https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm）或[时间复杂度的权力（）]（ https://stackoverflow.com/questions/5231096/time-complexity-of-power） – Dukeling

您的解决方案不是O（1）空间，意思是：您的空间/内存不是常量但取决于输入！

newx=xor^(2**num)

这是按位异或超过log_2(2**num) = num位，其中num是你输入一个号码，导致log_2(2**num) = num位结果。

因此n=10 = log_2(2^10) = 10 bits,n=100 = log_2(2^100) = 100 bits。它正在线性增长（不是恒定的）。

它也不Ø中（n）的时间复杂度为你有：

在所有n个数外环
- 和非恒定/非O（1）inner-循环（见上）
- 假设：XOR是在关于输入的比特表示不恒定
  - 这不是像总是处理;但物理支持这种说法（钱德拉塞卡极限，光速，...）

来源

2017-09-14 14:08:47 sascha

得到它谢谢你，它是O（n）的时间？ –

10个数字将导致11位，而不是1024位。 100个数字将是101位。空间复杂度是线性的，而不是指数。 – interjay

10位可以表示1024个数字，位数不像您所说的那么大，只有计算出的数量与xor相同。 – maraca

你的问题实际上是很难回答。通常在处理复杂性时，有一个假定的机器模型。 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是重复的，因此，你可以从阵列的总XOR异或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 ）空间，以及从0开始的O（n）时间绝不会使用比n更多的位（即大约ln（n）位）。

来源

2017-09-14 15:05:44

另一种方法是对所有值进行异或，如果n不是2^x-1，则用n + 1，n + 2，...结果，直到你达到2的幂减1，我认为它会需要较少的异或操作，但并不那么优雅。 – maraca

计算xor 1..n似乎效率低下。另一种解决方案是在任何语言中使用模数运算的数字（例如C中的无符号数）进行相加，然后减去它们的总和（即（（无符号）n）*（n + 1）/ 2）。 –

它不是'n/log（n）'存储单元，它是'n/k'，其中'k'是每个位置的位数。 –

找到O（1）的空间和O（n）的时间

回答

相关问题