如何在線性時間內對列表中的不同值進行計數？

我可以考慮對它們進行排序，然後逐個遍歷每個元素，但這是nlogn。是否有一個線性方法來計算列表中的不同元素？如何在線性時間內對列表中的不同值進行計數？

來源

2012-12-13 polerto

更新： - 獨特與唯一

如果您正在尋找「獨一無二」值（如，如果你看到一個元素「JASON」不止一次，是不是比沒有再獨特，不應該計算在內）

您可以通過做線性時間HashMap;）

（廣義/語言無關的想法是Hash table）

一個HashMap /哈希表的每個條目是<KEY, VALUE>對，其中密鑰是唯一的（但在這對他們的相應的值沒有限制）

步驟1：

迭代通過所有列表中的元素一次：爲O（n）

對於列表中看到的每一個元素，檢查它是否在HashMap中已經O（1），攤銷
- 如果不是，將其添加到與列表中作爲關鍵元素的值，數量HashMap的時候，你已經看到，只要價值這個值O（1）
- 如果是的話，增加的次數，你已經看到了這個KEY到目前爲止O（1）

第二步：

迭代通過HashMap和計數與VALUE等於正好1（因而唯一的）鍵爲O（n）

分析：

運行時：爲O（n），攤銷
空間：O（U），其中U是不同值的數量。

但是，如果你正在尋找「獨特」值（好像要算多少不同元素有中），使用HashSet，而不是一個HashMap /哈希表，然後簡單地查詢HashSet的大小。

來源

2012-12-13 17:22:52

這是如何在列表中找到多個唯一值，並且問題是關於找到許多不同的值。要計算不同的值，請使用[HashSet]（http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html）。只需將列表中的每個元素添加到HashSet並檢查其基數。 – user1871166

難道你不想在步驟2中計算HashMap中的所有值，而不是隻計算值爲1的那些值？這樣做只會計算出現一次的元素，例如。列表{PAT，PAT，STEVE，JOEL}將導致值2（僅STEVE和JOEL出現一次），而不是3個不同名稱的正確值。 – Jason

注意！這裏存在解釋差異：我的假設是，如果您看到特定值2次或更多次，則它不再是「獨特」/「獨特」 - 但我會將其編輯得更加清晰。 –

您可以刪除重複計數到不同值的任務適應this extremely cool O(n)-time and O(1)-space in-place algorithm - 只需數等於最後的澳哨兵值值的數量（n）的通過，並減去從列表的大小。

來源

2012-12-13 17:46:04

將列表中的每個元素添加到HashSet，然後檢查HashSet的size（基數），它是列表中不同值的數量。

來源

2012-12-13 17:54:13 user1871166

如何在線性時間內對列表中的不同值進行計數？

回答

相關問題