T137 只出现一次的数字 II

题目描述

思路：记录每个数字出现的次数，判断如果只出现一次，就返回，为了减少所用时间，用字典来存储减少查询所花费的时间。

代码如下：

class Solution:
   def singleNumber(self, nums: List[int]) -> int:
       mydic = {}
       for i in nums:
           if mydic.get(i) is None:
               mydic[i] = 1
           else:
               mydic[i] += 1
       for i in nums:
           if mydic[i] == 1:
               return i

结果如下：

看到最后一行小字，不用额外的空间

参考Krahets大佬的题解137. 只出现一次的数字 II（有限状态自动机 + 位运算，清晰图解） - 只出现一次的数字 II - 力扣（LeetCode）学习后，可以只使用O(1)的空间复杂度，可以用列表的第一项来存储。没有使用状态机，因为所有的值求和求模完毕后就是结果（二进制）

思路为统计每个数的二进制表示后求和然后对每个位上的和模3求余数，结果为01串，化为十进制就是结果。

可以记录一个记录位的信息，当 当前位和记录位值都为1且加数也为1的时候，将当前位和记录位都记为0即可。

理解：如果只出现两次的话，相当于直接做求和模2即可，因为两个相同的数加上后，位上肯定是2的倍数，而只有一个的要求的那个数则会保留下来。出现三次，就需要三进制模三，但是专门写个三进制有些过于复杂了，所以用进位来记录2

对于当前位纪录位和加数位的输入，得到的是新的当前位和记录位：

新当前位D的卡诺图为

新记录位E的卡诺图为

因此

D=~B·C+A·~C

E=B·~C+A·~B·C

其中~表示非，·表示与，+表示或，^表示异或

代码如下所示：

class Solution:
   def singleNumber(self, nums: List[int]) -> int:
       length = len(nums)
       # 如果长度为1，那么返回该元素
       if length == 1:
           return nums[0]
       # 如果不为1，那么必然大于等于4
       #进行初始化,相当于记录位为0，加上第二个数
       # 初始化中num[0]就是A，num[1]就是C，B=0
       iniD = nums[1] | nums[0]&~nums[1]
       iniE = nums[0]&nums[1]
       nums[0] = iniD
       nums[1] = iniE
       # 循环中A B C分别是num[0]num[1]num[i]
       for i in range(2, length):
           D = nums[0]&~nums[i] | ~nums[1]&nums[i]
           E = nums[1]&~nums[i] | nums[0]&~nums[1]&nums[i]
           nums[0] = D
           nums[1] = E
       return D

结果如下：

此时确实是没有创建新的对象元素，空间复杂度为O(1)