爲什麼我的算法O（1）額外的空間複雜度？

我從codefights解決了這個問題：爲什麼我的算法O（1）額外的空間複雜度？

注意：寫一個O（n）時間複雜度和O（1）額外的空間複雜性的解決方案，因爲這是在真正的面試時你會被要求做的。

給定一個數組a，它只包含範圍從1到a.length的數字，找到第二個匹配項具有最小索引的第一個重複數。換句話說，如果有多個重複的號碼，則返回第二次出現的索引小於第二次出現的次數。如果沒有這樣的元素，則返回-1。

int firstDuplicate(int[] a) { 
    HashSet z = new HashSet(); 
    for (int i: a) { 
     if (z.contains(i)){ 
      return i; 
     } 
     z.add(i); 
    } 
    return -1; 
}

我的解決方案通過了所有的測試。但是我不明白我的解決方案如何滿足O（1）額外的空間複雜度要求。哈希表的大小與輸入成正比，所以我認爲它是O（n）空間複雜度。 Codefights是否錯誤地測試了我的算法，還是我誤解了一些東西？

來源

2017-09-23 Sendai

'只有數字範圍從1到a.length' - 您能否澄清一下？ – xenteros

根據我的經驗，空間限制通常由在線評委測試。他們大多是在那裏，所以你知道在實際的採訪中，你可能會被要求這樣做。你是對的，你的算法顯然不使用額外的額外空間。 – Shalan

@xenteros關於這個問題還不清楚嗎？ – Sendai

您的代碼沒有O（1）輔助空間複雜性，因爲如果給定一個包含所有不同元素的數組，那麼該散列集可以增長到n的大小。

我的猜測是在線測試基礎架構沒有檢查內存使用情況，也沒有正確檢查內存使用情況。如果您想要滿足空間限制，則需要返回並嘗試以不同的方式解決問題。

作爲提示，考慮重新排列數組元素。

來源

2017-09-23 19:41:49 templatetypedef

這在技術上是不正確的，有兩個原因。

首先，根據數組中的值，當int s變爲Integer s並添加到HashSet時，可能會有開銷。其次，儘管額外的內存大部分是與HashSet相關的開銷，但該開銷與該組的大小成線性比例。（請注意，由於它們已經存在於陣列中，因此我不計算其中的元素。）

通常，通過設置可使用的內存量限制來測試這些內存限制。像這樣的解決方案我預計會低於上述閾值。

來源

2017-09-23 19:41:43

如果你能夠修改輸入數組，你可以用O(n)時間複雜度修復你的問題，而不使用外部存儲器。

public static int getFirstDuplicate(int... arr) { 
    for (int i = 0; i < arr.length; i++) { 
     int val = Math.abs(arr[i]); 

     if (arr[val - 1] < 0) 
      return val; 
     arr[val - 1] = -arr[val - 1]; 
    } 

    return -1; 
}

來源

2017-09-23 20:14:16

該解決方案也是O（n）空間。 – xenteros

@xenteros是的，我把我的第一個例子移回去了。我正在考慮使用這種方法來查找所有獨特的重複項，但似乎是不可能的。 –

爲什麼我的算法O（1）額外的空間複雜度？

回答

相關問題