题目
-
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1：
输入：nums = [2,2,1]
输出：1
示例 2：
输入：nums = [4,1,2,1,2]
输出：4
示例 3：
输入：nums = [1]
输出：1
法一、排序加遍历
- 思路：先对数组进行排序，然后遍历数组，每次跳过出现两次的元素。当找到一个元素与下一个元素不相等时，即找到了只出现一次的元素。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums = sorted(nums)
for i in range(len(nums)-1):
if nums[i] != nums[i+1]:
return(nums[i])
i+=1#错误，应该一次跳过两个元素
-
第一次解决时，没通过，很多地方没考虑到：应该一次跳过两个元素；数组只有一个元素的情况未考虑到；只出现一次的元素在最后一个位置的情况
-
如果找到了只出现一次的元素，就直接返回该元素。如果整个循环结束后仍未找到只出现一次的元素，说明只出现一次的元素在数组的末尾，因此我们返回 nums[-1]。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort() # 先对数组进行排序
n = len(nums)
i = 0
while i < n:
if i == n - 1 or nums[i] != nums[i + 1]:#数组只有一个元素或者找到不相等的元素时
# 当前元素与下一个元素不相等，即找到了只出现一次的元素
return nums[i]
i += 2 # 跳过出现两次的元素
# 如果只出现一次的元素在数组末尾
return nums[-1]
- 时间复杂度为 O(nlogn)。
法二、异或性质
- 异或运算：
任何数和自己做异或运算，结果为0，即 a⊕a=0
任何数和0做异或运算，结果还是自己，即 a⊕0=a
异或运算中，满足交换律和结合律，也就是 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
x = 0
for num in nums: # 1. 遍历 nums 执行异或运算
x ^= num
return x; # 2. 返回出现一次的数字 x
时间复杂度O(N):线性遍历nums使用O(N)时间，异或操作使用O(1)时间
空间复杂度O(1)：辅助变量a，b，x，y使用常数大小额外空间
法三、reduce()函数
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
return reduce(operator.xor, nums)#xor表示异或
- reduce()函数会对参数序列中元素进行累积，接收的参数：一个函数 f，一个list，实例如下：
from functools import reduce
def add(x, y) : # 两数相加
return x + y
sum1 = reduce(add, [1,2,3,4,5]) # 计算列表和：1+2+3+4+5
sum2 = reduce(lambda x, y: x+y, [1,2,3,4,5]) # 使用 lambda 匿名函数
print(sum1) #15
print(sum2) #15