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

Question

有一个"file"的数据集——文件名，后面跟着32位数字——类似于文件的哈希值。

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

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

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

Answer 1

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

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

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

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

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