LeetCode如何找出只出现一次的数字

这篇文章主要为大家展示了“LeetCode如何找出只出现一次的数字”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“LeetCode如何找出只出现一次的数字”这篇文章吧。

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

对集合进行切片，生成三个集合，找到与另外两个集合不同的集合缺少的数字。如集合[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

以上是“LeetCode如何找出只出现一次的数字”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！