leetcode 136. 只出现一次的数字 python
题目描述:
"""
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4
"""
方法1:
用列表存储数字,如果列表中不存在该数字,则添加进列表,如果列表中存在该数据则从列表中去除。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
list_num = []
for i in nums:
if i not in list_num:
list_num.append(i)
else:
list_num.remove(i)
return list_num[0]
【leetcode 136. 只出现一次的数字 python】
文章图片
方法2:
用集合计算,把所有数都放入集合中,集合中相加之和乘以2减去原来列表中的和为该题结果
class Solution:
def singleNumber(self, nums: List[int]) -> int:
set_nums = set(nums)
set_nums_sum = sum(set_nums) * 2#集合是可以直接sum求和的
nums_sum = sum(nums)
res = set_nums_sum - nums_sumr
eturn res
文章图片
方法3:
用异或表示,异或的三个性质:
1.所有数和0异或为该数本身。
2.自己与自己异或等于0。
3.异或满足交换律与结合律。
python 中的异或用 ^ 表示
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x,y:x^y , nums)
关于reduce的用法可以参考reduce的用法
文章图片
推荐阅读
- 午门传说
- 低头思故乡——只是因为睡不着
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 2018-09-03(李克富视角点评训练营81/90)|2018-09-03(李克富视角点评训练营81/90) 那只蛙从“井”爬出来又进入了“隧道”
- 早知道你是只飞鸟,我就应该把你关起来
- 杀死一只知更鸟
- 只要有一台手机,人人都可以是摄影师
- 穷得只剩下一个人
- 全职妈妈在4岁孩子眼中只是一个loser