给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
示例1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4
该题想让我们找出数组里的唯一元素,直觉上我们会使用哈希表,将重复的元素记录下来判断,但哈希表会占用额外的内存空间,如:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
h = defaultdict(int)
res = 0
for n in nums:
h[n] += 1
if h[n] > 1:
res -= n
else:
res += n
return res
如果用位运算异或,将重复元素排除,即可找出不重复的元素了,用异或的原因是:
则最终实现如下:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for n in nums:
res ^= n
return res
这时候是常量级别的空间复杂度。
感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/109.html
邮箱:glowrypauky@gmail.com
QQ: 892413924