from typing import List
class Solution:
    # 第一种是我想的办法
    def singleNumber(self, nums: List[int]) -> int:
        # 首先进行排序
        nums.sort()
        # 然后判断重复的数字，数组中的数字必定为奇数个，
        # 如果循环没有跳出，那么数组的最后一个数字一定为不重复的数字
        for index in range(1,len(nums),2):
            if nums[index] != nums[index - 1]:
                return nums[index -1]
        return nums[-1]
    # 第二个答案是官方解答
    def singleNumber1(self, nums: List[int]) -> int:
        # 位运算，任何数和零位运算都为本省
        # 位运算，是二进制的异或运算。
        # 100  ^  110 = 10   #这是二进制。
        # 这就相当于将数组中的每一个数都分解为二进制。
        # 然后将每一位进行异或运算。最后留下来的二进制就是没有重复的。
        num = 0
        for index in range(len(nums)):
            num ^= nums[index]
        return num
A = Solution()
print(A.singleNumber1([1,2,2,3,3,4,4]))
print(A.singleNumber1([1,1,2,2,3,3,4,4,5]))