首页 技术 正文
技术 2022年11月23日
0 收藏 587 点赞 2,449 浏览 805 个字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

思路

很容易想到的2个方法是:

  1. 用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]
  1. 用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
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,088
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,564
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,413
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,186
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,822
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,905