找到給定數字中唯一元素的最快方法

Question

我有n個數字。 n < = 1000000.每個數字將是正整數且小於10^9。

確定只會有一個號碼出現一次，休息會發生兩次甚至幾次。

我知道的最短的解決方案是所有數字異或的結果。我想知道

• 什麼是標準XOR解決方案的複雜性。
• 我們如何優化解決方案。

Answer 1

XOR算法是正確的算法和最快的算法。緩慢的部分是你閱讀輸入的方式。

例如，C中的scanf比使用getchar（或更好的getchar_unlocked）手動處理自己的數字算法要慢。在你提到的SPOJ問題上，只要做出這樣的改變，我就從1.35s提高到了0.14s。我相信剩餘的0.04在網站上獲得最佳時間只是由於比我的代碼更好的低級IO。

Answer 2

XORing所有的數字將是O（n）的複雜性，因爲你只需要訪問每個元素一次。

根據您的要求，我無法想出任何進一步優化此方法的方法。異或是一個非常便宜的操作，問題的本質要求您至少訪問一次元素：否則，您不可能知道哪個值是唯一的。

Answer 3

你可以去散列。原始解決方案是使用唯一編號作爲散列表的關鍵字。如果可能的話，那麼你可以使用哈希算法。一個簡單的例子是使用數字作爲數組中的索引。現在，空間會太多（我的意思是太多），但可以進一步優化。