LeetCode 137. Single Number II

Posted on | In |
Words count in article: 409 | Reading time ≈ 1

题目

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

Note:

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

Example 1:

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

Example 2:

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

思路

对于Single Number问题及其变种，可以做一下总结：

  • 通解: 对于任意参数为k,p问题，输入数组每个元素都出现了k次，只有一个只出现了p次，求那个单独的只出现p次的数，都可以用求和的方式解决。例如原始的Single Number问题，是k=2, p=1，则可以用两倍所有非重复元素的和，减去原数组即可，即2 * sum(set(nums)) - sum(nums)
  • 位操作方法: 关键是利用相同的数偶数次按位异或结果为0，奇数次按位异或是自身，灵活运用mask和与操作来改变或者检验某一位。

对于此题，可以当作模拟三进制运算。
Reference.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# class Solution(object):
#     def singleNumber(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         return (3*sum(set(nums))-sum(nums))/2

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, three = 0, 0, 0
        for num in nums:
            two |= one & num  #当新来的为0时，two = two | 0，two不变，当新来的为1时，（当one此时为0，则two = two|0，two不变；当one此时为1时，则two = two | 1，two变为1
            one ^= num  #新来的为0，one不变，新来为1时，one是0、1交替改变
            three = one & two  #当one和two为1是，three为1（此时代表要把one和two清零了）
            one &= ~three  #把one清0
            two &= ~three  #把two清0
        return one