java - 数据结构设计设计

Question

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

计算段落中单词的频率。

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

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

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

我创建列表或地图的地图

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

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

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

可以使用哪些其他方法？

Answer 1

一旦你有了你的（词，频率）对，你可以创建一个数组，按频率排序，然后进行二分搜索。这将减慢对 O(log n) 的访问速度，但如果这是限制的话，您可以使用大约一半的内存。

除此之外，我没有看到比你已经在做的更好的了。