leetcode/Python/single-number-ii.py at master · OnlyChristmas/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
'''
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:

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

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


'''

# 类似题目 leetcode 136 、260


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 所有数字相加后每个二进制位除以三，会将所有出现三次的数字都消除掉。 需要一个固定的32为的辅助数组空间O(1)
        if not nums : return 0
        length = len(nums)
        res,bitSum = 0, [0 for _ in range(32)]
        for i in nums:
            bitMask = 1
            for j in range(31,-1,-1):
                if i & bitMask != 0:
                    bitSum[j] += 1
                bitMask <<= 1

        for i in range(32):
            res = res << 1
            res += bitSum[i] % 3
        return res


        # 二进制模拟三进制 ，详见  https://cloud.tencent.com/developer/article/1341825
        # if not nums : return 0
        # a, b = 0, 0
        # for i in nums:
        #     a = (a ^ i) & ~b
        #     b = (b ^ i) & ~a
        # return a