arrays - 未排序的移位数组的位移

Question

我们有一个未排序的数组，其中包含不同的条目 a_1、a_2、... a_n，我们还知道一个移位数组 a_(n-k)、...a_n、a_1、a_2、...目标是找到给定这两个数组的位移 k。当然还有最坏情况的线性算法 O(n)。但我们能做得更好吗？

有暗示，答案与k分布有关。如果 k 在 0 和 n 之间均匀分布，那么我们必须在 O(n) 内完成。如果 k 以其他方式分布，可能会有一些更好的方法。

Answer 1

如果数组中没有重复项(不同的条目)，我将使用 while 循环并从 0 开始递增索引值 k 并从头开始一次比较两个项目，一个从头开始。比如array1[k] === array2[0] 或者array1[n-k] === array[0] 和索引值k 应该是上述比较返回真值后的位移。