我们有一个未排序的数组,其中包含不同的条目 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 以其他方式分布,可能会有一些更好的方法。
最佳答案
如果数组中没有重复项(不同的条目),我将使用 while 循环并从 0 开始递增索引值 k
并从头开始一次比较两个项目,一个从头开始。比如array1[k] === array2[0]
或者array1[n-k] === array[0]
和索引值k
应该是上述比较返回真值后的位移。
关于arrays - 未排序的移位数组的位移,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40325299/