不幸的是，拥有一个按值排序的映射(映射到的对象(并不是一件事。相反，你可以有一个集合，它的关键点根据频率进行排序，但如果频率是当时的关键点，你就无法在事先不知道频率的情况下查找该集合中的条目，这就消除了练习的要点。
我在Java中有一个哈希映射，格式为HashMap<String, Integer> frequency。键是一个字符串，我在其中保存电影的名称，值是所述电影的频率。
我的程序接受用户的输入，所以每当有人将视频添加到收藏夹时，我都会进入哈希图，并增加其频率。
现在的问题是，有一点我需要拍最频繁的电影。我发现我可以在这个leetcode问题中使用bucketsort或heapsort(查看第一条注释(，但我不确定它在我的情况下是否更有效。我的哈希图不断更新，因此如果一个频率发生变化，我需要再次调用排序算法。
根据我的理解，构建地图需要O(N(时间，其中"N"是即使有重复的电影数量，因为它需要添加到频率中，这为我提供了"M"个独特的电影标题。这是否意味着，对于任何给定的k，堆排序将导致O(M*log(k((和bucketsort O(M(？
脑海中浮现的一种策略是拥有两个独立的数据结构。一个是让你根据电影的名称查找实际对象，另一个是自我排序：
@Data
public class MovieFrequencyTuple implements Comparable<MovieFrequencyTable> {
@NonNull private final String name;
private int frequency;
public void incrementFrequency() {
frequency++;
}
@Override public int compareTo(MovieFrequencyTuple other) {
int c = Integer.compare(frequency, other.frequency);
if (c != 0) return -c;
return name.compareTo(other.name);
}
}
有了它：
SortedSet<MovieFrequencyTuple> frequencies = new TreeSet<>();
Map<String, MovieFrequencyTuple> movies = new HashMap<>();
public int increment(String movieName) {
MovieFrequencyTuple tuple = movies.get(name);
if (tuple == null) {
tuple = new MovieFrequencyTuple(name);
movies.put(name, tuple);
}
// Self-sorting data structures will just fail
// to do the job if you modify a sorting order on
// an object already in the collection. Thus,
// we take it out, modify, put it back in.
frequencies.remove(tuple);
tuple.incrementFrequency();
frequencies.add(tuple);
return tuple.getFrequency();
}
public int get(String movieName) {
MovieFrequencyTuple tuple = movies.get(movieName);
if (tuple == null) return 0;
return tuple.getFrequency();
}
public List<String> getTop10() {
var out = new ArrayList<String>();
for (MovieFrequencyTuple tuple : frequencies) {
out.add(tuple.getName());
if (out.size() == 10) break;
}
return out;
}
每个操作都摊销O(1(或O(logn(，甚至是前10个操作。因此，如果你运行一百万次"增加电影的频率，然后获得前10次"，其中n=我们这样做的次数，那么最坏的情况是O(nlogn(性能。
注意：对构造函数、getter等使用lombok——如果你不喜欢，让你的IDE生成这些东西。