0136. 只出现一次的数字

0136. 只出现一次的数字 #

  • 标签:位运算、数组
  • 难度:简单

题目大意 #

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。要求不能使用额外的存储空间。

解题思路 #

如果没有时间复杂度和空间复杂度的限制,可以使用字典来存储每个元素出现的次数,或者用集合来存储数字,如果集合中没有该数字,则将该数字加入集合,如果集合中有了该数字,则从集合中删除该数字,最终成对的数字都被删除了,只剩下单次出现的元素。

如果考虑不使用额外的存储空间,就需要用到位运算中的异或运算。对 n 个数不断进行异或操作,最终可得到单次出现的元素。

异或运算 ⊕ 的三个性质:

  1. 任何数和 0 做异或运算,结果仍然是原来的数,即 a ⊕ 0 = a。
  2. 数和其自身做异或运算,结果是 0,即 a ⊕ a = 0。
  3. 异或运算满足交换率和结合律:a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b。

代码 #

1
2
3
4
5
6
7
8
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        ans = 0
        for i in range(len(nums)):
            ans ^= nums[i]
        return ans
本站总访问量  次  |  您是本站第  位访问者