java - 你会建议什么搜索算法或数据结构？

Question

我有很多SortedSet<Long>结构：

1, 2, 5, 8, 10, 35, 77, ...
5, 9, 35, 50, 132, ...
2, 4, 8, 15, 17, 23, ...
... hundreds of thousands of such rows...

我需要找到一个数字，比如说，50。在这个例子中（如果只有三组）它是77. 集合的数量是巨大的 - 数十万。你会建议什么算法？

Answer 1

如果我理解正确，这是我的想法：

Collection<SortedSet<Long>> sets = //...

long minAfter50 = Long.MAX_VALUE;
for (SortedSet<Long> set : sets) {
    final Long first = set.tailSet(51L).first();
    minAfter50 = Math.min(minAfter50, first);
}

这是想法：

• 遍历所有输入集
• 裁剪所有小于或等于 50 的值
• 取裁剪集的第一个参数（保证大于 50）
• 计算上一步收集的最小值

更新（基于@beerbajay评论）：如果 SortedSet 实际上是 a TreeSet，则以下代码可能会执行得更好。此外，我确保每组中都有任何大于 50 的值：

long minAfter50 = Long.MAX_VALUE;
for (TreeSet<Long> set : sets) {
    final Long higher = set.higher(50L);
    if (higher != null && higher < minAfter50) {
        minAfter50 = higher;
    }
}

Answer 2

如果这就是您允许的所有预计算，那么您唯一能做的就是在每个 SortedSet 上调用 tailSet 并找到最小值。

如果您允许一些额外的数据结构，最简单的做法是跟踪所有集合的并集，然后您只需调用 tailSet 即可。

我怀疑这也不是你想要的答案。也许您可以更好地描述您的限制条件？

Answer 3

set 实现为二叉搜索树，最大的数总是在最后。您可以更轻松地搜索大于 50 的数字，始终获得每组中大于 50 的第一个数字。