淘先锋技术网

首页 1 2 3 4 5 6 7

需求:

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

说明:

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

示例1:

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

示例2:

输入:[4, 1, 2, 1, 2]
输出:4  
废话少说直接上代码:
class Solution:
	def singleNumber(self, nums):
	"""
	:type nums: List[int]
	:rtype: int
	"""
	# 法一:
	# import collections
	# dct = collections.Counter(nums)
	# for num, count in dct:
	# 	if count < 2:
	# 		return num  

	# 法二:
	res = 0  
	for num in nums:
		res ^= num
	return res
总结:

刚开始拿到这个题,我想大多数人第一想到的就是使用字典,法一使用的就是类似字典的映射,它使用了Python标准库里面的collections,这个库里面有个方法Counter,它能将可迭代对象里面的元素进行统计,最后的结果是一个字典结构,以元素为key,元素出现的次数为value,最后我们只要判断value小于2的元素就可以了。但是,这种方法的时间复杂度不是最佳。

我们来看一下法二,它的原理是利用异或运算,0与任何数字进行异或运算它的结果都为其本身,而任意两个相同的数字进行异或运算结果都为0。因为它底层使用的是数字的二进制运算,例如:
0和5做异或运算:
000 ^ 101
根据同0异1法则,结果为101,即5;
8和8做异或运算:
1000 ^ 1000
结果为0000,即0;
对数组[4, 1, 2, 1, 2]中的元素进行异或运算:
100 ^ 001 -----> 101
101 ^ 010 -----> 111
111 ^ 001 -----> 110
110 ^ 010 -----> 100,即结果为4。

所以如果考虑到不使用额外的空间并且时间复杂度为线性,法二是个不错的选择。