LeetCode Single Number II

Problem

Given an 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?

一个整型数组，除一个元素外，其余的元素都出现三次，要求不用额外内存，线性时间内找到这个元素

Python 实现

# Given an 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?

# author li.hzh

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        once = twice = three_times = 0
        for val in nums:
            twice |= once & val
            once ^= val
            three_times = once & twice
            once &= ~three_times
            twice &= ~three_times
        return once


print(Solution().singleNumber([1, 3, 1, 1, 3, 5, 3, 6, 6, 6]))

分析

这个题确实想了很久很久。最终解决问题的思路是这样。

先是受到一个思路的启发，就是出现三次，那么可以把每一位的数字相加，然后除以3，把不能整除的位留下来。这个位组成的数字就是那个single number。不过这个思路需要对每个数字的每一位进行遍历，效率不达标。但是，却给了我很好的启发。让我关注每一位的元素是否为1。

用3个变量来分别记录，元素出现1次，2次，3次对应位的情况。当出现3次后。1次和2次对应的位置就清0，最后剩下的元素的位置就保存在1次的那个变量中。这里利用还是异或的特性。

可以简单的过一下这个过程。[3,3,3,2] 为例。

遍历第一个3时，按照设计语义，twice = 1， once =3 ，three_times = 0。继续。 第二个3，once = 0， twice = 3,（因为3出现两次），thre3_times = 0，继续 第三个3，once = 3， twice = 3 ，three_times = 3。重置1,2对应的位置。

如此下去，最后得到的就是2。

这里理解的关键，就是once twice和three_times，不要看成具体的数字，而是对数字每一位变化情况的描述。 once 异或元素。对于某一位的变化规律是1,0,1 twice 当出现2次以上时，对应的位是1 three = once & twice ，出现3此时，自然为1。