Unsorted shifted array offset

Question

We have one unsorted array with different entries a_1, a_2, ... a_n, and we also know the shifted array a_ (nk), ... a_n, a_1, a_2, ... The goal is to find the offset k with these two arrays. Of course, there is the worst linear O (n) algorithm. But can we do better than that?

There is a clue that the answer has something to do with the distribution of k. If k is evenly distributed between 0 and n, then we must do this within O (n). If k is distributed otherwise, there might be a better way.

Answer 1

If there are no duplicates in the array (different records), I would do it with a while loop and increase the index value kstarting from 0 and comparing two elements at once from the beginning and one from the end. For example, array1[k] === array2[0]or array1[n-k] === array[0], and the index value kshould be an offset as soon as the above comparison returns true.

Answer 2

There is an O (sqrt (n)) solution, as shown based on @greybeard's hint.

The first sqrt (n) elements are hashed from the first list. In the second list, consider the items promoted by sqrt (n) at each point in time.

However, we may ask if there is a solution that can be close to O (k) (or less!) If k is small and n is large. In fact, I maintain that there is an O (sqrt (k)) solution.

. , :

2 - ( , HashMap , , - ). . . - . , , . 3 - .

: , . , , , , .

, p, p * (p + 1)/2 . , k , p sqrt (2k), O (sqrt (k)) .

Answer 3

, , a[0] b[0], , a[1] b[1]. a's, :

a[0] == b[0] or b[0] in hash?   => known k's: 0
a[1] == b[2] or b[2] in hash?   => known k's: 0,1,2
a[2] == b[5] or b[5] in hash?   => known k's: 0,1,2,3,4,5
a[3] == b[9] or b[9] in hash?   => known k's: 0,1,2,3,4,5,6,7,8,9
a[4] == b[14] or b[14] in hash? => known k's: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
...

( , O(sqrt n) .)

Answer 4

, -. (n-k) O (1).