题解 | #只出现一次的数字#

题目分析

1. 题目给出了我们一个数组列表
2. 该列表中只有一个数字出现了一次，剩下的数字都是出现两次的
3. 题目要求我们最终返回只出现一次的对应数字

方法一：暴力搜索（超时）

• 实现思路

  • 首先花一轮遍历数组的时间代价对每一个数组中的数字num作数字统计操作

  • 然后在数组中计数num出现的次数

  • 如果num只出现一次则返回该数字为本题答案

class Solution:
    def singleNumber(self , nums: List[int]) -> int:
        # write code here
        for num in nums:				# 遍历数组
            if nums.count(num) == 1:	# 对于数组中每一个数字进行计数统计
                return num				# 返回找到的数字结果

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$表示数组的空间大小，由于遍历需要$O(n)O(n)$代价，计数统计需要$O(n)O(n)$代价，因此结果是$O(n^2)O(n^2)$的代价
• 空间复杂度：$O(1)O(1)$，只引入线性级别的空间消耗

方法二：位运算

• 实现思路
  • 我们可以在暴力的基础上优化时间代价
  • 因为我们知道数字在数组中的出现规律，只有一个数字出现了一次，剩下的数字都是出现两次
  • 因此我们可以利用异或的计算规则，对数组中的所有数字进行异或运算，对于出现两次的数字会在异或运算中最后结果变回0，而只出现一次的数字会在最终的异或运算结果中保留下来

class Solution:
    def singleNumber(self , nums: List[int]) -> int:
        # write code here
        res = 0                # 目标返回结果
        for num in nums:       # 遍历数组
            res = res ^ num    # 异或运算
        return res             # 返回结果

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中$nn$表示数组的空间大小，只进行了一轮的循环开销
• 空间复杂度：$O(1)O(1)$，只引入了常量级别的空间开销