Single Number

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目很简单,但有难度的是不使用额外空间。也就是说要使用一些比较 trick 的方法。
这让我想到以前碰到的一题,交换 Array 中两元素的位置,同样不使用额外空间,最后解法是使用 bitwise operation。
按照这思路去解题的话,很快就想到 xor 运算,相同得 0,不同得 1,题目就引刃而解了。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in nums:
result ^= i
return result

Single Number II

于是题目升级了。
Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

由于出现次数是 3 次,我们不能再方便地使用 xor 运算了。那有没有哪个现成的运算可以拿来用?显然没有。那我们只能直接做出类似 xor 的运算了。
具体公式的形成可以参考 An General Way to Handle All this sort of questions. 以及 Detailed explanation and generalization of the bitwise operation method for single numbers
其中 b 存放的是只出现一次的值,a 存放的是出现两次的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
b = 0
for c in nums:
ta = (~a & b & c) | (a & ~b & ~c)
b = (~a & ~b & c) | (~a & b & ~c)
a = ta
return a | b

Single Number III

又是一个变形。
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

既然还是出现两次,那自然还是使用 xor 运算。但如果和 I 一样,直接对数组进行 xor 运算,会无法识别那两个数字。有什么办法能把那两个数字分开?
我们可以先对数组进行 xor 运算,对得到的结果进行分析。由于两个数肯定不相等,那得到的结果中必有一位为 1。我们再根据该位将数组分成两部分,然后分别进行 xor 运算,就可以得到剩下的两个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = 0
a = 0
b = 0
for num in nums:
xor ^= num
mask = 1
while (xor & mask == 0):
mask = mask << 1
for num in nums:
if num & mask:
a ^= num
else:
b ^= num
return [a, b]

参考