题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

  1. 输入: [2,2,1]
  2. 输出: 1

示例 2:

  1. 输入: [4,1,2,1,2]
  2. 输出: 4

解答 1：

  1. #
  2. # @lc app=leetcode.cn id=136 lang=python3
  3. #
  4. # [136] 只出现一次的数字
  5. #
  8. # @lc code=start
  9. class Solution:
  10.     def countLetter(self, arr, v):
  11.         count = 0
  12.         for j in arr:
  13.             if j == v:
  14.                 count = count + 1
  15.         return count
  17.     def singleNumber(self, nums) -> int:
  18.         for (i, v) in enumerate(nums):
  19.             if self.countLetter(nums, v) == 1:
  20.                 return v
  23. Solution().singleNumber([2, 2, 1,1,3322,22,22])
  25. # @lc code=end

Note

两层循环
一层负责遍历列表，另一层则对遍历的每一个值再进行一次遍历，统计这个值出现的次数
复杂度是O(n^2)
结果是超时
image.png

解答 2：

  1. #
  2. # @lc app=leetcode.cn id=136 lang=python3
  3. #
  4. # [136] 只出现一次的数字
  5. #
  8. # @lc code=start
  9. class Solution:
  10.     def singleNumber(self, nums) -> int:
  11.         k = nums[0]
  12.         for (i, v) in enumerate(nums):
  13.             if i == 0: continue
  14.             k = (k ^ v)
  15.         return k
  18. Solution().singleNumber([2, 1, 2])
  20. # @lc code=end

Note

使用异或运算^

  1. 交换律：a ^ b ^ c <=> a ^ c ^ b
  2. 任何数于0异或为任何数 0 ^ n => n
  3. 相同的数异或为0: n ^ n => 0

[2, 2, 1]
2^2 = 10^10 = 0
0^1 = 00^01 = 1

[2, 1, 2]
2^1 = 10^01 = 3
3^2 = 11^10 = 1