最佳的方式找到一個數組

什麼是找到一個數組的唯一號碼的數量的最佳方式唯一號碼的數量。一種方法是將它們添加到HashSet，然後查找hashset的大小。有沒有其他的方式比這更好。最佳的方式找到一個數組

我只需要唯一號碼的數量。他們的頻率不是必需的。

任何幫助表示讚賞。

感謝，哈里什

2011-06-07 Harish

您的解決方案對我來說很不錯。 – planetjones 2011-06-07 15:47:38

我的意思是程序使用的最佳內存和計算時間。在HashSet方法中，對於每個Add操作可能涉及哈希和其他操作。我想檢查是否有存儲數據的地方，我可以使用任何XOR或OR運算符組合或其他方式來獲取唯一編號的數目 – Harish 2011-06-07 18:01:20

你不說了已知的數字，但如果1）它們是整數，2）你知道的範圍（最大值和最小值）和3）的範圍不是太大，那麼你就可以分配長度與天花板（範圍/ 32）相等的整數（假設32位整數）全部初始化爲零。然後遍歷數據集並將每個數字對應的位設置爲1.最後，計算1位數。

來源

2011-06-07 20:30:36

是的，他們是整數，範圍是知道的，不是太大。我也只是採用這種方法。這是我目前使用的。但只是檢查是否有這樣我不需要存儲/檢查計數。但是我使用的是大小範圍數組。相反，我可以使用範圍/ 32，這將減少我的數組大小....我感覺像使用二元運算符的一些屬性，我們可以直接實現計數。但在那之前我會通過這種方法 – Harish 2011-06-08 07:40:02

一些語言有內置的工具。 Java具有可動態擴展的BitSet，並具有'cardinality（）'函數來返回設置的位數。 C++通過'bitset :: count（）'具有類位（固定大小）。（據我所知，C＃和Matlab都有bitsets，但缺少返回基數的函數）。如果你想自己推出，有一些有趣的位計算算法在這裏討論[http://gurmeet.net/puzzles/fast-bit-counting-routines /）和[here]（http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32位整數） – 2011-06-10 04:36:04

一個簡單的算法是循環通過列表中添加號碼設置爲你說一個哈希值，但每次檢查它是否已經在集合，如果不加1到運行計數。然後，當您完成循環列表時，您將在運行計數的最終值中包含不同元素的數量。下面是一個python例如：

count=0 
s=set() 
for i in list: 
    if i not in s: 
     s.add(i) 
     count+=1

編輯：我因爲在後臺集合可被實現爲稀疏陣列和在該陣列的額外循環中使用的運行計數，而不是檢查一組的長度可以是需要檢查每個散列是否有相應的值。運行計數避免了潛在的額外開銷。

來源

2011-06-07 15:42:56 murgatroid99

不需要運行計數。只要詢問哈希集到底有多大。 – 2011-06-07 15:45:10

@Ted我在我的回答中添加了一個解釋。 – murgatroid99 2011-06-07 15:49:26

你好，但這是一個不必要的查找。和更多的代碼 – Magnus 2011-06-07 15:52:41

我會建議數組排序第一，尋找後獨特的元素。

來源

2011-06-07 16:02:29 Piotr

什麼是內存中的權衡對你願意接受更少的CPU週期？哪一個對您的最佳解決方案更重要？ counting sort的變體在空間效率非常低，但非常快。

對於更大的數據集，你會想要使用散列，這是HashSet中已經這樣做。假設你願意承擔實際存儲數據的開銷，那麼就去看看你的想法吧。它具有附加的優點，即使用任何語言來實現標準庫都更簡單。

來源

2011-06-07 16:05:35 Sysyphus

對於這個問題，「最優」意味着什麼？ – 2011-06-07 16:09:54

因爲這是在算法下，所以我會假定最短的平均或最差情況下的運行時間，但實用性通常會在某些時候出現。 – Sysyphus 2011-06-07 16:19:33

我的意思是程序使用的存儲器和計算時間的最佳週期。在HashSet方法中，對於每個Add操作可能涉及哈希和其他操作。我想檢查是否有存儲數據的地方，我可以使用任何XOR或OR運算符組合或以其他方式獲取唯一編號的數字 – Harish 2011-06-07 18:01:41

最佳的方式找到一個數組

回答

相關問題