Single Number
「找单数」系列题,技巧性较强,需要灵活运用位运算的特性。
Question
- leetcode136
- lintcode: (82) Single Number
Given 2*n + 1 numbers, every numbers occurs twice except one, find it.
Example
Given [1,2,2,1,3,4,3], return 4
Challenge
One-pass, constant extra space
题解
根据题意,共有2*n + 1
个数,且有且仅有一个数落单,要找出相应的「单数」。鉴于有空间复杂度的要求,不可能使用另外一个数组来保存每个数出现的次数,考虑到异或运算的特性,根据x ^ x = 0
和x ^ 0 = x
可将给定数组的所有数依次异或,最后保留的即为结果。
class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
ans = A[0]
for i in range(1, len(A)):
ans = ans ^ A[i]
return ans
class Solution:
# @param {integer[]} nums
# @return {integer}
def singleNumber(self, nums):
return reduce(operator.xor, nums)
class Solution:
# @param {integer[]} nums
# @return {integer}
def singleNumber(self, nums):
return reduce(operator.xor, nums)