Python 刷Leetcode题库，顺带学英语单词（34）

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.    [#136]

Note:

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

   Examples:

Input: [2,2,1]
    Output: 1
    Input: [4,1,2,1,2]
    Output: 4

题意：非空整数数组中，除一个数字只出现过1次其它数都出现2次，找出这个数字来。

方法一：.count()计数

1. >>> a=[4,1,2,1,2]
2. >>> [_ for _ in a if a.count(_)==1][0]
3. 4
4. >>>

方法二：异或^运算性质：任何整数数异或它本身都等于0

>>> a=[2,2,1]
>>> t=[0];[t.append(t[-1]^_) for _ in a]
[None, None, None]
>>> t[-1]
1
>>>
>>> b=[4,1,2,1,2]
>>> t=[0];[t.append(t[-1]^_) for _ in b]
[None, None, None, None, None]
>>> t[-1]
4
>>> 

>>> def func(nums):
  res = 0
  for i in range(len(nums)):
    res ^= nums[i]
  return res
>>> a=[2,2,1]
>>> b=[4,1,2,1,2]
>>> func(a)
1
>>> func(b)
4
>>> 

Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.   [#137]

Note:

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

   Examples:

Input: [2,2,3,2]
    Output: 3
    Input: [0,1,0,1,0,1,99]
    Output: 99

题意：非空整数数组中，除一个数字只出现过1次其它数都出现3次，找出这个数字来。