找到數組中的一個非重複元素？

我有一個n元素的數組，其中只有一個元素不重複，否則所有其他數字重複> 1次。數組的範圍沒有限制。找到數組中的一個非重複元素？

一些解決方案是：

有沒有更好的解決辦法？

2012-04-20 Luv

哈希表實際上並沒有佔用太多的空間：'O（n）'。如果數組太大以至於必須在原地進行，那麼您可能需要使用外部排序。 – bdares 2012-04-20 05:01:55

散列的空間複雜度至多爲'O（n）'（可能有'C> x'，對於一些小的'x'，取決於實現，儘管如此）。我喜歡「排序第一方法」。 – 2012-04-20 05:01:56

是的，但合併排序（就地）的空間複雜度爲零。 – Thilo 2012-04-20 05:03:25

一種通用的方法是實現一種分段技術（其中散列法就是這樣一種技術），使用它們的標識（比如索引）將元素分佈到不同的「桶」中，然後找到最小尺寸的桶你的情況）。我相信這個問題也被稱爲少數族元素問題。將有儘可能多的水桶，因爲你的設備中有獨特的元素。

通過散列這樣做是因爲碰撞，以及如何你的算法可能會處理這個問題。某些關聯數組方法（如try和可擴展哈希）似乎並不適用，因爲它們更適合字符串。上述的

的一種應用是給Union-Find data structure。您的集合將成爲存儲桶，您需要爲陣列中的每個元素調用MakeSet（）和Find（），每次調用的開銷爲$ O（\ alpha（n））$，其中$ \ alpha（n） $是非常緩慢增長的逆阿克曼函數。你可以把它看作是一個常數。

當元素已經存在時，你必須做聯合。通過一些更改來跟蹤基數最小的集合，該解決方案應該可以工作。該解決方案的時間複雜度爲$ O（n \ alpha（n））$。

你的問題似乎也鬆散有關Element Uniqueness problem。

2012-04-20 17:53:40 rrufai

如果您有嚴格的空間限制，請嘗試多次掃描。

說輸入有n個元素，你只能在你的記憶中保存m個元素。如果你使用散列表方法，在最壞的情況下，你需要處理n/2個唯一的數字，所以你需要m> n/2。如果沒有那麼大的m，可以將n個元素劃分爲k =（max（input）-min（input））/（2m）組，然後繼續掃描n個輸入元素k次（最差case）：

第一次運行：你只是散列/ get/mark /任何元素的值< min（input）+ m * 2;因爲在範圍內（min（輸入），min（輸入）+ m * 2），最多有m個獨特元素，您可以處理它。如果你幸運的話，你已經找到了唯一的，否則繼續。

第二運行：僅在範圍內具有值元素進行操作（分鐘（輸入）+ M * 2，分鐘（輸入）+ M * 4），和等等，等等

以這種方式，你妥協的時間複雜度爲O（KN），但你必然O（M）的空間複雜度

2012-04-21 22:30:06 HelloWorld

兩個思路來我的腦海：

一個smoothsort可能比一個更好的選擇所引用的mergesort爲您的需要給出它在內存使用O（1），O（nlogn）在最差的cas e作爲合併排序，但在最佳情況下爲O（n）;
基礎上splay tree的（反向）的想法，你可以做一個類型的樹一旦被使用（而不是向上的伸展樹），這將推動葉子朝底部。這仍然會給你一個O（nlogn）種類的植入，但好處將是尋找獨特元素的O（1）步驟，它將是根。排序算法是O（nlogn）+ O（n）的總和，該算法將是O（nlogn）+ O（1）

否則，你說，使用基於散列溶液（如哈希實現的集合）會導致一個O（n）算法（O（n）插入並添加一個計數引用到它和O（n）遍歷你的集合來找到唯一的元素），但你似乎不喜歡內存用法，但我不知道爲什麼。內存很便宜，這幾天......

2012-05-15 05:04:25 Soravux

回答