数据结构来缓存最频繁的元素

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