Leetcode 136.只出现一次的数字 By Python
2024-09-14 00:10:27
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
思路
很容易想到的2个方法是：
- 用list.count()方法统计只出现一次的个数，很不幸的是，这个超时了
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
X = [i for i in nums if nums.count(i) == 1]
return x[0]
- 用collections.Counter()，会返回一个字典，key为元素，value为元素出现的次数，只要找到value小于2的就好了，虽然没有超时，但是效率也不够让人满意，才超越了10%左右
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
x = collections.Counter(nums)
for key,value in x.items():
if value < 2:
return key
改进的版本
提交后看了最快的代码，思路是运用按位异或运算符，当两对应的二进位相异结果为1，真值表如下:
| a | b | c |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以看出如果有两个元素是相等的，按位异或的结果会是0，而0与任何数都等于这个数本身（也就是保存了这个数）
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for num in nums:
result = result ^ num
return result
最新文章
- jScrollPane 美化滚动条
- jQuery回调、递延对象总结（下篇) —— 解密jQuery.when方法
- 浅谈javascript函数节流
- Bootstrap3.0学习第九轮(CSS补充)
- jq 的连续动画
- OC基础(7)
- 第 2 章 代理模式【Proxy Pattern】
- 输出特殊符号，可以用单引号'引文'：echo 'Hello World !'
- SELinux开启和关闭
- js-数组算法收集版（转）
- poj 1161 Walls
- 前端模块化工具--webpack使用感受
- C语言程序设计进阶 翁恺 第4周编程练习
- #云栖大会# 移动安全专场——APP渠道推广作弊攻防那些事儿（演讲速记）
- C#操作Control异步工具类
- Hadoop Mapreduce的shuffle过程详解
- POJ 3368
- RocketMQ实战快速入门
- 20175314 《Java程序设计》第五周学习总结
- （转）CSS书写规范、顺序