175 - 260 只出现一次的数字3 - 040

137 - 只出现一次的数字2

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2] 输出: 3

示例 2:

输入: [0,1,0,1,0,1,99] 输出: 99

解答

https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/

https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-shu-zi-dian-lu-she/

1的问题是，全部是2个，只有一个是1。结论是用异或

异或相当于无进位的二进制加法，因此这道题里面，多数是三个，就要用无进位的三进制加法。即有一种运算，0#1=1, 1#1=2, 2#1 = 0

因此需要两个比特来记录信息，而且只需要00, 01, 10这三个状态，所以用两个变量，one和two，第一位和第二位。

然后就是画卡诺图。我也是谷歌了半天才知道是啥玩意

num\one,two	00	01	11	10
0	0	0	x	1
1	0	1	x	0

• 左边第一列，是下一个数字

• 第一行，是旧的one，two

• 中间的内容，是结果值，即新的01值

然后圈图就知道了逻辑。。

• newOne = (one & ~num) | (two & num)

• newTwo = (~one & ~two & num) | (two & ~num)

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

Runtime: 60 ms, faster than 81.87% of Python3 online submissions for Single Number II.

Memory Usage: 14.6 MB, less than 53.33% of Python3 online submissions for Single Number II.

不知道为啥反正能成功版本

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

Runtime: 60 ms, faster than 81.87% of Python3 online submissions for Single Number II.

Memory Usage: 14.5 MB, less than 53.33% of Python3 online submissions for Single Number II.

推广

https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

给一个数组，其他数都出现k次(k>1)，有一个数出现p次p>=1, p%k!=0，找到那个特别的数

就，虽然题解很详细，但是位操作如此僵硬，我也看不太懂。。

• k=2, p=1

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

Runtime: 88 ms, faster than 86.12% of Python3 online submissions for Single Number.

Memory Usage: 15.3 MB, less than 8.20% of Python3 online submissions for Single Number.

• k=3, p=1

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

Runtime: 64 ms, faster than 68.05% of Python3 online submissions for Single Number II.

Memory Usage: 14.5 MB, less than 60.00% of Python3 online submissions for Single Number II.

• k=5, p=3

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

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5] 输出: [3,5]

注意：

• 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。

• 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解答

数组

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        data = []
        for num in nums:
            if num not in data:
                data.append(num)
            else:
                data.remove(num)
        return data

Runtime: 868 ms, faster than 6.00% of Python3 online submissions for Single Number III.

Memory Usage: 14.3 MB, less than 100.00% of Python3 online submissions for Single Number III.

位运算

https://leetcode.com/problems/single-number-iii/discuss/68900/Accepted-C%2B%2BJava-O(n)-time-O(1)-space-Easy-Solution-with-Detail-Explanations

思路就是，拆成两个数组，分别对齐用1的异或方法

var singleNumber = function(nums) {
  let sign = 0
  for (const num of nums) {
    sign ^= num
  }
  sign &= -sign

  let result = [0, 0]
  for (const num of nums) {
    if ((num & sign) == 0) {
      result[0] ^= num
    } else {
      result[1] ^= num
    }
  }
  return result
};

Runtime: 60 ms, faster than 85.91% of JavaScript online submissions for Single Number III.

Memory Usage: 37.4 MB, less than 66.67% of JavaScript online submissions for Single Number III.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        sign = 0
        for num in nums:
            sign ^= num
        # 获取最后一位1
        sign &= -sign
        result = [0]*2
        for num in nums:
            if (num & sign) == 0: # 该位没有置1
                result[0] ^= num
            else:                                 # 该位已置1
                result[1] ^= num
        return result

Runtime: 56 ms, faster than 94.72% of Python3 online submissions for Single Number III.

Memory Usage: 14.7 MB, less than 50.00% of Python3 online submissions for Single Number III.