0

所以我正在遍历一个 BinaryTree 并且节点包含字符串以及字符串在读取文件时是否出现多次。我只是在寻找在阅读文件时出现最多的前 10 个单词，所以基本上我只是在比较一个 int 值。

我的问题是我试图找出一种有效的方法来比较和插入一个新节点，如果它们的计数值更大。所以说我有一棵树...

   5
  /  \
 3    10
/       \

1 15

假设数组大小只有 3。我从 1 开始，因为数组在 5 之前都是空的，它看起来像在达到 5 之后......

[1],[3],[5]

当我达到 10 时，它比一切都重要，但我想保持排序，所以我需要将 3 转换为 1、5 转换为 3 和 10 转换为 5。我想知道是否有更有效的方法来做到这一点在每个更高的数字之后移动。它读取超过 10k+ 字的文本文件，所以我希望它尽可能快。

如果不同的数据结构对此更好，请告诉我。我在考虑队列或链表，但我认为数组浪费的空间更少，因为它的大小只有 10。我是一名学生，所以也要温柔：-x。

4

2 回答 2

1

一种方法是使用几个数据结构。使用 Map 和 Min-Heap 的建议方法如下：

  • 当您从文件中读取单词时，请保持其在哈希映射中的计数（单词，word_count）。
  • 保持大小为 10 的最小堆。每当您更新地图中的单词时，增加其计数。现在将此计数与最小堆的顶部元素进行比较。如果 word_count > value_at_top，则替换顶部元素并堆化。
  • 完成文件读取后，此堆将包含堆中最常见的 10 个元素
于 2012-10-31T06:55:27.937 回答
0

嗯，你总是可以把它扔到一个未排序的 ArrayList 中并运行一个排序：

List<Node> myArrayList = new ArrayList<Node>();
//Arbitrarily add subtract, replace, etc.
Collections.sort(myArrayList);

这就是我的建议！

于 2012-10-31T06:28:21.367 回答