algorithm - 编程 : find the first unique string in a file in just 1 pass

Question

给定一个很长的产品名称列表，找到第一个唯一的产品名称(恰好出现一次)。您只能在文件中迭代一次。

我正在考虑获取 HashMap 并将 (keys,count) 存储在双向链表中。基本上是一个链接的 HashMap 谁能优化这个或提供更好的方法

Answer 1

因为你只能迭代列表一次，所以你必须存储

• 每个字符串只出现一次，因为它可能是输出
• 他们在列表中的相对位置
• 出现不止一次的每个字符串(或者它们的散列，如果你不害怕的话)

值得注意的是，您不必存储出现多次的字符串的相对位置。

你需要

• 高效存储字符串集。哈希集是一个很好的候选者，但 trie 可以根据字符串集提供更好的压缩。
• 按值高效查找。这排除了一个裸列表。哈希集是明显的赢家，但 trie 也表现良好。您可以将 trie 的叶子存储在哈希集中。
• 高效查找最小值。这需要一个链表。

结论:

对字符串集使用链接哈希集，并使用标志指示它们是否唯一。如果您正在为内存而战，请使用链接的 trie。如果链接的 trie 太慢，则将 trie 叶子存储在 HashMap 中以供查找。仅包含链接列表中的唯一字符串。

总的来说，您的节点可能如下所示:Node:{Node[] trieEdges, Node trieParent, String inEdge, Node nextUnique, Node prevUnique}; Node firstUnique, Node[] hashMap

如果您力求易于实现，则可以改为使用两个哈希集(一个链接)。