我有两个数字桶(无序的一维数据结构)，我想计算两个桶的任何元素之间的最小距离。有没有办法在 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)
看看我为什么需要这个以及我在 previous question edition 中想到了什么.
最佳答案
让有n总数。
1. 用二进制写出所有数字。 ==> O(n)
2. 根据是来自 B1 还是 B2，在每个数字中附加 0 或 1。 ==> O(n)
3. 对它们进行快速排序，忽略第一位。 ==> O(n log n)平均
4. 对于整个列表，遍历排序顺序。对于每两个相邻数字 u和 v ，如果它们同时来自 B1 或 B2，则忽略。
否则，设置 tmp <-- abs(u-v)每当tmp > abs(u-v) .
因此，tmp是到目前为止的最小距离，在相邻数字内。
决赛tmp是答案。 ==> O(n)
总计:==> O(n log n)平均
关于c++ - 找出两个数字桶之间的最短距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40870850/