Leetcode每日一题-有序数组中的单一元素

原题链接：有序数组中的单一元素

这题是比较容易想到二分查找的解法，就只需要结合题意明确二分之后如何查找。稍微摸索一下规律可以发现：

只有一个数只出现一次，那么数组的元素必定是奇数个，二分之后需要比较中间数与左右两边是否出现，未出现则只出现一次，直接返回；往左查找还是往右查找还需要考虑两边数值的个数奇偶性，因为只出现一次的数只可能出现在个数为奇数的一边（去除掉与中间数相等的数后）

O(n)写法：

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        i = 0
        while i < (n - 1):
            if nums[i] != nums[i + 1]:
                return nums[i]
            i += 2
        return nums[n - 1]

O(logn)写法：

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        def get_once(arr, left, right):
            # 只剩一个元素直接返回
            if left == right:
                return arr[left]
            mid = (right + left) // 2
            L = right - mid
            if (arr[mid] != arr[mid - 1]) and (arr[mid] != arr[mid + 1]):
                return arr[mid]
            elif (L % 2):
                # 奇数个
                return get_once(arr, mid + 1, right) if (arr[mid] == arr[mid - 1]) else get_once(arr, left, mid - 1)
            else:
                # 偶数个
                return get_once(arr, left, mid - 2) if (arr[mid] == arr[mid - 1]) else get_once(arr, mid + 2, right)
        return get_once(nums, 0, n - 1)