一、题目要求
二、题目背景
位运算：或，异或，与，移位
三、解题思路
（1）要求算法时间复杂度是线性的，O(n)，想到的是先将列表排序，排序后相同的数值两两之间前后相邻，进行偶数次循环，判断两两数值是否相等即可。需要注意的是考虑列表只有 一个数字和最后一个是single number的情况。
运行结果见下，时间复杂度不高，但是很占内存。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
if len(nums)==1:
return nums[-1]
else:
for i in range(0,len(nums)-2,2):
if nums[i]-nums[i+1]!=0:
return nums[i]
if i==len(nums)-3 :
return nums[-1]
（2）这道题属于位运算操作，所以采用异或操作其实更简便
知识点：0^a=a; b^a^a=b
或：只要有1就得1
与：只要有0就得0
异或：只要相等就得0
位移动:
从运行结果来看，还是很耗内存，执行时间也比上面的慢一点，主要是异或操作循环了列表中所有值
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
