找到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）的時間

回答

相關問題