arrays - Find the unduplicated element in a sorted array

Question

Source : Microsoft Interview Question

Given a sorted array, in which every element is present twice except one which is present single time, we need to find that element.

Now a standard O(n) solution is to do a XOR of list, which will return the unduplicated element (since all duplicated elements cancel out.)

Is it possible to solve this more quickly if we know the array is sorted?

Answer 1

O(log n)是的，您可以通过进行二分搜索来使用排序性来降低复杂性。

由于数组已排序，因此在缺少元素之前，每个值都占据了点2*k和2*k+1数组中（假设从 0 开始索引）。

因此，您转到数组的中间，例如 index h，并检查索引h+1是否h为偶数或奇数。如果缺少的元素在后面出现，则这些位置的值相等，如果在前面出现，则值不同。重复直到找到丢失的元素。h-1h

Answer 2

对数组进行二进制“搜索”（相当遍历），检查两个邻居，如果两者都与中间的值不同，那么您就有了解决方案。这是O(log n).

Answer 3

是的，数组已排序，因此我们可以应用二进制搜索来查找单个元素。让我们看看单个元素的出现模式。元素总数总是奇数，单个元素仅出现在偶数索引处

元素总数 9，单个元素总是出现在偶数索引处。当 时(end_index - start_index) % 4 == 0，单个元素出现在中间。

if A[mid-1] == A[mid] --> single element left side
if A[mid] == A[mid+1] --> single element right side

元素总数 11，单个元素总是出现在偶数索引处。当 时(end_index - start_index) % 4 != 0，单个元素不在中间出现。

if A[mid] == A[mid+1] --> single element left
if A[mid-1] == A[mid] --> single element right

元素总数 13，单个元素总是出现在偶数索引处。当 时(end_index - start_index) % 4 == 0，单元素也出现在中间。

if A[mid-1] == A[mid] --> single element left side
if A[mid] == A[mid+1] --> single element right side

下面是 Python 代码：

class Solution:
    def singleNonDuplicate(self, A):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(A)

        def binarySearch(A, start, end):
            if start == end:
                return A[start]

            if start < end:

                mid = int(start + (end - start)/2)

                if A[mid-1] < A[mid] < A[mid+1]:
                    return A[mid]
                if end - start == 2:
                    if A[end] != A[end-1]:
                        return A[end]
                if end - start == 2:
                    if A[start] != A[start+1]:
                        return A[start]
                if A[mid] == A[mid+1]:
                    if int(end-start)%4 == 0:
                        return binarySearch(A, mid+2, end)
                    else:
                        return binarySearch(A, start, mid-1)

                elif A[mid-1] == A[mid]:
                    if int(end - start)%4 == 0:
                        return binarySearch(A, start, mid-2)
                    else:
                        return binarySearch(A, mid+1, end)

        return binarySearch(A, 0, L-1)


if __name__ == "__main__":

    s = Solution()
    A = [1,1,2,3,3,4,4,5,5,6,6]
    r = s.singleNonDuplicate(A)
    print(r)