algorithm - 如何对 32 位数字进行排序以查找唯一条目？

Question

有一个“文件”数据集 - 文件名，后面是 32 位数字 - 类似于文件的哈希值。

"file1" 6a9bd9a6 1df3b24b 7ab054dc
"file2" 6a9bd54e 1df3b24b 8cd054dc
"file3" 6a9bd9a6 7ab054dc

我将如何获得唯一文件，因此 s2 不是任何其他 s2 的前缀 - 这意味着该数字是唯一的。如果有两个相同的 s2，如果它们不是任何其他 s2 的前缀，它们都是唯一的。

我正在寻找一个快速的解决方案。我可以想出解决方案来比较每个字符串，但这太耗时且无效。另一种选择是以某种方式将 MySQL 引擎用于表，但我不确定如何。你能帮我吗？

score 2 · Accepted Answer

您可以使用trie来确保没有字符串是任何其他字符串的前缀。

当你插入你的 trie 时，你会检查这两种情况：

1）我是否通过了旧的叶节点？如果是这样，这意味着另一个字符串是我的字符串的前缀。
2）我想将已经存在的非叶子标记为叶子吗？如果是这样，我是另一个字符串的前缀。

这将是一个 O(N) 解决方案，其中 N 是字符串的数量（测量插入到 trie 中的数量）。每个插入运行其字符串的长度。

所以如果你想从这里创建哈希。您可以轻松地遍历特里树，然后在到达所需的叶子后使用有关是否有前缀节点的信息。每个叶子节点代表一个完整的路径，它知道它是否是另一个字符串的前缀。如果是前缀，那么它至少有 1 个子节点。

1 回答 1