要使用哪種數據結構？

我有這樣一個場景，我需要存儲的字符串的數和我需要回到前十弦它具有最大計數，要使用哪種數據結構？

例如，

String Count 
--------------------------------- 
String1 10 
String2 9 
String3 8 
. 
. 
. 
String10 1

我考慮使用散列表來存儲字符串和它的計數，但是很難從它中檢索前十個字符串，因爲我必須再次循環來找到它們。

此處有任何其他建議嗎？

來源

2012-08-02 Lokn

只需使用一個有序映射像

Map<Integer, List<String>> strings

，其中的關鍵是頻率值和值與頻率出現字符串列表。

然後，循環遍歷地圖，並通過值列表的內部循環，直到看到10個字符串。那些是最常見的10個之一。

隨着額外要求，該算法應該支持更新頻率：將字符串添加到像Map<String, Integer>一個地圖，關鍵是字符串和值實際頻率（增量，如果你的價值再次看到一個字符串）。之後將鍵/值對複製到我上面建議的地圖。

來源

2012-08-02 14:52:03

+1好主意...... – assylias 2012-08-02 14:53:41

如何在計算字符串時更新這樣的結構？（雖然沒有明確提及，但通常是用例）。 – ffriend 2012-08-02 15:01:10

讓我們來計算字符串出現的頻率並將其添加到此地圖中，並假設有10個字符串，每個字符串都出現10次，那麼此地圖將具有像1-字符串1這樣的條目.... string10，2-string1 ... string10類似地，它對地圖中的所有值都有相同的條目，是否有任何優化的解決方案。 – Lokn 2012-08-02 15:03:04

Priority Que。

你可以讓一個類來把它：

public class StringHolder{ 
    private String string; 
    private int value; 

    //Compare to and equals methods 
}

則按照當您插入，很容易獲得前10名。

來源

2012-08-02 14:50:25 Brinnis

如果字符串已經存在，那麼我只需要增加計數，如何找到特定的字符串對象呢？ – Lokn 2012-08-02 14:53:24

這將是一個相對緩慢的操作。你將不得不遍歷所有查找該String的對象。如果你這樣做了很多哈希映射可能會更好。您必須決定是否希望get top 10變慢，或者如果將數據結構中已有的內容更新得更慢。 – Brinnis 2012-08-02 14:59:57

@Lokn：你可以用一個哈希映射對字符串進行計數，然後使用優先級隊列來查找N個頻率最高的字符串。這將是2次通過，但漸近運行時間仍將攤銷O（n）。 – ffriend 2012-08-02 15:20:24

對於喜歡「找到前N的任何任務項目「優先隊列是完美的解決方案。請參閱Java的PriorityQueue類。

來源

2012-08-02 14:52:00 ffriend

我不知道，但我想這對於您需要的最合適的優雅類是番石榴的 http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/TreeMultiset.html

來源

2012-08-02 14:59:32

TreeMultiset可以使用，但它比HashMultiset有更多的開銷。它強加的順序是實際的鍵，而不是數。因此，您爲關鍵訂單付出的開銷被浪費了。 – Matt 2012-08-02 15:26:30

番石榴這將是對這個非常有用的一個HashMultiset。

HashMultiset<String> ms = Hashmultiset.create(); 
ms.add(astring); 
ms.add(astring, times); 


ImmutableMultiset<String> ims = Multisets.copyHighestCountFirst(ms); 

// iterator through the first 10 elements, and they will be your top 10 
// from highest to lowest.

來源

2012-08-02 15:04:15 Matt

爲此，您需要Max Heap數據結構。把它全部放入最大堆，並連續10次（或任何n次）清除。

如果您打算在數據加載到內存後繼續重用數據，則可能值得按值而不是堆排序。

來源

2012-08-03 17:01:04 Ambar

要使用哪種數據結構？

回答

相關問題