540. 有序数组中的单一元素

https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

解法一：累加

只适用于有序数组

观察可知，单一元素必出现在偶数下标。将数组元素累加，下标偶取正，奇取负即可。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        res = 0
        for i in range(len(nums)):
            res = res + nums[i] if i%2 == 0 else res - nums[i]
        return res

解法二：异或

同136. 找数组只出现一次的数字，适用于有序和无序数组。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        for num in nums[1:]:
            nums[0] ^= num    #取0号元素记录结果，节省空间
        return nums[0]

解法三：二分

主要思路：若成对出现在单一元素左侧，其下标应为（偶，奇），单一元素右侧为（奇，偶）。每次取中点，根据中点与其邻近元素是否相等，来判断单一元素是在中点左侧还是右侧。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left+right)//2
            if mid % 2 == 0:    #偶数
                if nums[mid] == nums[mid+1]:    #（偶，奇），单一元素在右边
                    left = mid
                else:   #在左边
                    right = mid
            else:    #奇数
                if nums[mid-1] == nums[mid]:    #（偶，奇），单一在右边
                    left = mid + 1
                else:   #在左边
                    right = mid - 1
        return nums[left]    #right也可以