找到两个数字桶之间的最短距离

Question

我有两个桶(无序,1维数据结构)的数字,我想计算两个桶的任何元素之间的最小距离.有没有办法找到不同桶中任何数字之间的最短距离O(1)？什么是我最好的选择？

Input
[B1] 1, 5, 2, 347, 50
[B2] 21, 17, 345

Output
2 // abs(347 - 345)

编辑

• 我希望有更多的查找而不是插入
• 任何桶中最小和最大元素之间的距离小于10 ^ 5
• 任何桶中的元素数量小于10 ^ 5
• 存储桶中的数字"几乎"排序 - 这些是事件的时间戳.桶中可能不到1%的元素出现故障
• 存储桶中的元素数量很少,但我需要以2k/sec的平均速率查找,并定期删除过时的存储桶并用新存储桶替换它们,因此我希望我的查找能够在 O(1)

看看为什么我需要这个以及我在之前的问题版本中想到的内容.

Answer 1

这是我的尝试：对每个桶进行排序，然后对它们进行某种合并排序，跟踪沿途的最小距离O(n+2.n/2.ln(n/2)) = O(n.ln(n))：：

sort buk1
sort buk2
min = INT_MAX
last = some value
do
    if top(buk1) > top(buk2)
        min = min(min, abs(top(buk1) - last))
        last = top(buk1)
        pop(buk1)
    else
        min = min(min, abs(top(buk2) - last))
        last = top(buk2)
        pop(buk2)
while !empty(buk1) and !empty(buk2)