數據結構來緩存最頻繁的元素

Question

想我讀整數流。流中可能會出現多次相同的整數。現在我想保留一個最頻繁出現的N個整數的緩存。緩存按流元素的頻率排序。

你將如何實現它在Java中？

Answer 1

使用Guava Multiset和sort it by frequency

Answer 2

爲INT創建一個對象模型，中創建一個Count屬性。創建一個擴展Vector集合的SortedVector集合。每次發生整數時，如果它不存在，則將其添加到向量中。否則，找到它，更新count屬性+ = 1，然後在Vector中調用Collections.sort（this）。

Answer 3

你知道號碼的範圍是多少？如果是這樣，那麼使用數組可能是有意義的。例如，如果我知道數字的範圍在0到10之間，那麼我會創建一個大小爲10的數組。該數組中的每個元素都會計算我看過給定數字的次數。然後，你只需要記住最常見的號碼。

例如

array[10]; 
freq_index = -1; 
freq_count = -1; 

readVal(int n){ 
    array[n]+=1; 
    if array[n] > freq_count 
    freq_index = n; 
    freq_count = array[n]; 
} 

當然，如果數字的分佈是稀疏的，這種方法是不好的。

我想嘗試一個優先級隊列。

Answer 4

你想使用二進制索引樹，在鏈接的代碼是C++，應該是相當簡單轉換成Java（AFAICT代碼是相同的）：

Paper Peter Fenwick

Implementation in C++

Answer 5

public class MyData implements Comparable<MyData>{ 
    public int frequency = 0; 
    public Integer data; 
    @Override 
    public int compareTo(MyData that) { 
    return this.frequency - that.frequency; 
    } 

} 

有它存儲在PriorityQueue