Python算法-情人节限定：在成双成对中寻找单身狗

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

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。（扎铁了，老心！！！ /(ㄒoㄒ)/~~）
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10

• 方法1：使用哈希表-遍历寻找

# 哈希表
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        hashTable = {}
        for num in nums:
            if num in hashTable:
                hashTable[num] += 1
            else:
                hashTable[num] = 1
        for item in hashTable:
            if hashTable[item] == 1:
                return item

• 方法2：位运算-同性相斥，异性相惜

# 位运算
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

• 方法3：双指针-鉴于数组是有序的，且相同元素成对出现

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            # 当mid是偶数，意味着nums[mid]前面有偶数个元素
            if mid % 2 == 0 and mid + 1 < len(nums):
                # 当mid和mid+1元素相等，意味着mid前面没有单一元素,否则单一元素在mid的前面
                if nums[mid] == nums[mid+1]:
                    left = mid + 1
                else:
                    right = mid - 1
            # 当mid是奇数，意味着nums[mid]前面有奇数个元素
            elif mid % 2 != 0 and mid + 1 < len(nums):
                # mid前面存在单一元素
                if nums[mid] == nums[mid+1]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                return nums[mid]
        return nums[left]

数据本身的情况决定了要采取哪一种算法，算法的时间复杂度和空间复杂度却大不相同！

时间和空间复杂度对比