algorithm - 尝试数字

Question

将 trie 或 DAWG 用于数字而不是字符串是个好主意吗？我有很多两个数字组合，并希望减少所需的内存大小。

我希望能够存储所有数字组合，但如果数据结构仅支持查询以检查给定组合中是否存在给定组合，我会很高兴。

Answer 1

我认为对 2 位数字的优化不会太大。但对于更长的数字，TRIE 绝对是一个很好的解决方案。

至于两位数组合，我认为最好使用大小为 100 的数组，该数组存储与 100 个两位数组合中的每一个相对应的标志（或计数，如果允许重复）。当然，如果只允许数字，您将只需要 90 个位置，因为以 0 开头的 10 个组合不是有效数字。插入数字时，只需在数组中设置相应的标志（恒定的计算复杂度）。当检查是否在集合中找到一个数字时，只需检查数组中的相应标志（同样是常数复杂度）。要恢复您拥有的所有数字，请遍历数组并打印所有设置了相应标志的数字。我的想法有点类似于设置排序，当允许重复计数排序时. 该解决方案还具有两种操作的最佳计算复杂度常数。