我一直在尝试解决以下问题。我有一系列积极的 可以很长的整数(数百万个元素)。这 序列可以在元素值中包含“跳跃”。前面提到的跳跃 表示两个连续元素彼此相差超过 1。
示例 01:
1 2 3 4 5 6 7 0
在上面提到的示例中,跳转发生在 7 和 0 之间。
我一直在寻找一些有效的算法(从时间的角度来看) 找到发生跳跃的位置。这个问题很复杂,因为 事实上,可能存在存在两次跳跃且其中一次跳跃的情况 是我正在寻找的跳跃,另一个是我要寻找的环绕 我不是在寻找。
示例 02:
9 1 2 3 4 6 7 8
这里 9 和 1 之间的第一个跳转是回绕。第二次跳跃之间 4和6是我正在寻找的跳转。
我的想法是以某种方式修改二分搜索算法,但我不确定由于环绕的存在是否可能。值得一提的是,最多只能发生两次跳转,并且在这些跳转之间对元素进行排序。有人有什么想法吗?预先感谢您的任何建议。
最佳答案
您无法找到有效的解决方案(有效意味着不查看所有数字,O(n)),因为您无法通过查看少于所有数字来得出有关数字的任何结论。例如,如果您只查看每隔一个数字(仍然是 O(n),但更好的因子),您将错过像这样的双跳:1 5 3
。您可以而且必须查看每个数字并将其与其邻居进行比较。您可以分割工作负载并使用多核方法,但仅此而已。
更新
如果您遇到特殊情况,即列表中只有 1 个跳转,而其余的已排序(例如 1 2 3 7 8 9
),您可以相当有效地找到此跳转。您不能使用普通的二分搜索,因为列表可能未完全排序,并且您不知道要搜索的数字,但您可以使用指数搜索的缩写,它有一些相似之处。
我们需要以下假设才能使该算法发挥作用:
- 只有 1 个跳转(我忽略了“环绕跳转”,因为从技术上讲它不在任何后续元素之间)
- 列表按其他方式排序,并且严格单调递增
有了这些假设,我们现在基本上是在寻找单调性的中断。这意味着我们正在搜索 2 个元素和 b 之间有 n 个元素但不满足 b = a + n
的情况。如果两个元素之间没有跳转,则这一定是正确的。现在您只需要找到不能以非线性方式满足此要求的元素,即指数方法。这个伪代码可能是这样的算法:
let numbers be an array of length n fulfilling our assumptions
start = 0
stepsize = 1
while (start < n-1)
while (start + stepsize > n)
stepsize -= 1
stop = start + stepsize
while (numbers[stop] != numbers[start] + stepsize)
// the number must be between start and stop
if(stepsize == 1)
// congratiulations the jump is at start to start + 1
return start
else
stepsize /= 2
start += stepsize
stepsize *= 2
no jump found
关于c - 二分查找修改,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55119401/