LeetCode刷题DAY 6：只出现一次的数字II

LeetCode刷题DAY 5：只出现一次的数字升级版，进一步深入理解位运算，灵活运用异或、非、与。

1

题目描述

给定一个非空整数数组，只有一个数字出现一次，其余出现三次，找出只出现一次的数字。如输入[3,4,5,4,3,3]，输出5。

2

解题

思路一：集合差值

对集合进行切片，生成三个集合，找到与另外两个集合不同的集合缺少的数字。如集合[2,2,3,2]，先对集合进行排序，得到[2,2,2,3]，通过切片生成集合[2,3]、[2]、[2]，比较集合之间元素差别，得到输出结果3。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort() 
        a=len(set(nums[::2]))
        b=len(set(nums[1::2]))
        if a==b:
            return list(set(nums[::3]) - set(nums[2::3]))[0]
        else:
            return list(set(nums[::3]) - set(nums[1::3]))[0]

思路二：位运算

通过set方法时空复杂度都是O(N)，位运算可以使得空间复杂度降为O(1)。在LeetCode刷题DAY 5：只出现一次的数字中使用的“异或”其实就是同一状态出现两次则归零，即0->1->10=0的变化，在本题中则是要让同一状态出现三次归零，即00->01->10->11=00，可见这里需要用两个bit进行状态记录。

这里需要注意的是，要对two、one两位分别计算。对于one，当two=1时，不管输入是什么下一步的one都为0，当two=0时，输入1则one=～one，输入0则one不变。对于two，依赖于one变化后的状态，one新状态为1时，two则为0，one新状态为0时，输入1则two=～two，输入0则不变。因为出现三次就归零，所以one最后保留的是只出现了一次的值。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one,two = 0,0
        for i in nums:
            one = one^i & ~two
            two = two^i & ~one
        return one

当然，对集合进行遍历，通过哈希表记录每个数字出现次数的方法也是可以的，时空复杂度也都是O(N)，代码与Day 5思路一一致，此处不再赘述。