塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-136 只出现一次的数字

最初想法:

方法一:排序,遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <2:
return nums[0]
nums = sorted(nums)

i = 0
while i < len(nums)-1:
if nums[i] != nums[i+1]:
return nums[i]
else:
i+=2
return nums[i]

方法二:

建立一个hash表,统计每个数字出现的次数,缺点是需要辅助空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <2:
return nums[0]

mylist= []
for elem in nums:
if elem not in mylist:
mylist.append(elem)
else:
mylist.remove(elem)
return mylist[0]

官方:

异或运算(推荐)

1
2
3
4
5
异或运算,
任何数和0做异或运算,结果仍然是原来的数,即a@0=a
任何数和其自身做异或运算,结果是0,即a@a=0
异或运算满足交换律和结合律,即 a@b@a=b@a@a=b@(a@a)=b@0=b
所以将数组中的所有数字进行异或运算就能得到出现一次的那个数字
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
"""
if len(nums) <2:
return nums[0]

for i in range(1, len(nums)):
nums[0] = nums[0]^nums[i]

return nums[0]
if help:小手一抖点个广告 or 大手一挥资助一下