3

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

我正在考虑采用哈希图并将（键，计数）存储在双向链表中。基本上一个链接的哈希图可以任何人优化这个或提供更好的方法

4

3 回答 3

2

由于您只能迭代列表一次，因此您必须存储

  • 每个字符串只出现一次，因为它可能是输出
  • 它们在列表中的相对位置
  • 每个出现多次的字符串（或者它们的哈希，如果你不害怕的话）

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

你需要

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

结论：

对字符串集使用链接的哈希集，并使用一个标志来指示它们是否是唯一的。如果您正在为记忆而战，请使用链接的特里。如果链接的 trie 太慢，则将 trie 叶存储在哈希图中以供查找。仅包括链表中的唯一字符串。

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

如果您努力实现易于实施，则可以使用两个哈希集（一个链接）。

于 2013-01-16T17:56:47.007 回答
0

以下算法在 O(N+M) 时间内解决它。在哪里

N=字符串数

M = 放在所有字符串中的字符总数。

步骤如下：

`1. Create a hash value for each string`

`2. Xor it and find the one which didn't have a pair`

Xor 有一个有用的属性，如果你执行 a xor a=0 和 b xor 0=b。

为字符串生成哈希值的提示：使用 27 基数系统，并给 aa 值 1，ba 值为 2，依此类推，直到 z 得到 26，所以如果字符串是 "abc"，我们计算哈希值如： H=3*(27 power 0)+2*(27 power 1)+ 1(27 power 2) =786 您可以使用模运算符使散列值足够小以适合 32 位整数。如果您这样做留意冲突，这基本上是两个不同的字符串，但由于模运算而获得相同的哈希值。大多数情况下，我猜你不会需要它。

所以计算每个字符串的哈希，然后从第一个哈希开始并保持异或，结果将保存没有一对的字符串的哈希值。 注意：这仅在字符串成对出现时才有用。这仍然是一个好主意，这就是我回答它的原因。

于 2013-01-16T17:56:48.450 回答
0

使用链接的哈希图是显而易见的。否则，您可以使用 TreeMap 样式的数据结构，其中字符串按计数排序。因此，一旦您完成读取输入，如果存在唯一字符串，则树的根是唯一的。与链接的哈希映射不同，插入最多需要 O(log n) 而不是 O(n)。您可以阅读 TreeMaps，了解如何将基本的 TreeMap 扩充为您需要的内容。同样在您的链接哈希图中，您可能需要花费 O(n) 才能找到您的第一个唯一键。使用 TreeMap 样式的数据结构，您的查找是 O(1) - 根。即使存在更多唯一键，您遇到的第一个键也将是根。随后的将是根的孩子。

于 2013-01-17T16:03:17.377 回答