java - 数据结构设计设计

Question

以下是我做过几次的场景..

计算段落中单词的出现频率。

我创建一个 map 并存储计数。所以我的 map 包含

  <Today, 10>
  <the, 123>
  <hello,1>
  <dont, 20>

现在另一种情况来了，识别计数为 100 或 30 的单词

我创建列表 map 或 map

<10, [today,...]>
   <123,[the,...]>

或者 <10, 2> <123,1> 基本上我有两张 map 来处理所有的工作.. 这工作正常，对一个的任何更新，另一个都必须更新。

检索和插入时间几乎是 O(1)。但这不是那么有效的内存。

可以使用哪些其他方法？

Answer 1

一旦你有了你的(词，频率)对，你就可以创建它们的数组，按频率排序，并进行二分搜索。这会减慢对 O(log n) 的访问速度，但如果这是约束条件，您可以使用大约一半的内存。

除此之外，我看不出有什么比您已经在做的更好的了。