在连续的重复元素数组中查找单个元素

Question

给定一个元素数组,其中除了单个元素之外,每个元素都被重复.此外,所有重复的元素彼此连续.

我们需要找出该单个元素的索引.

注意:

1. 数组可能无法排序

2. 预期时间O(logn)

3. 元素范围可以是任何东西.

O(n)是微不足道的.但我怎么能找出登录？给按位运算符一个想法,但没有任何结果.

另外,我无法在这个问题中使用这个陈述,所有重复的元素都是相互连续的.

Ex:  2 2 3 3 9 9 1 1 5 6 6
     output 5

Answer 1

它可以在O(logn)中完成,检查是否arr[2k] == arr[2k+1], k>=0- 如果是,那么不同的元素是AFTER 2k+1,如果不是 - 那么它是之前的2k+1.

这允许您通过检查中间值来有效地修剪每一步的一半数组,并且仅在问题的一半上进行递归,从而得到O(logn)整体.

Python代码:

def findUnique(arr,l,r):
    if r-l < 2: 
        return (arr[l],l)
    mid = (r-l)/2 + l
    if mid % 2 != 0:
        flag = -1
    else:
        flag = 0
    if (mid == 0 or arr[mid-1] != arr[mid] ) and (mid == len(arr)-1 or arr[mid] != arr[mid+1] ):
        return (arr[mid],mid)
    if arr[mid+flag] == arr[mid+1+flag]:
        return findUnique(arr,mid,r)
    return findUnique(arr,l,mid)