转自网友题解

题目

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

说明：

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

示例 1:

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

示例 2:

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

解题思路

• 二进制下不考虑进位的加法：本题为 136. 只出现一次的数字
  的拓展，136 题中我们用到了异或运算。实际上，异或运算的含义是二进制下不考虑进位的加法，即：, , , （不进位）
• 三进制下不考虑进位的加法：通过定义某种运算 #，使得 0 # 1 = 1，1 # 1 = 2，2 # 1 = 0。在此运算规则下，出现了 次的数字的二进制所有位全部抵消为 ，而留下只出现 次的数字二进制对应位为 。因此，在此运算规则下将整个 arr 中数字遍历加和，留下来的结果则为只出现 次的数字。
• 代码分析： 请结合代码注释和图表理解。
  • ones ^= num：记录至目前元素num，二进制某位出现次（当某位出现次时有 ，与共同表示「出现次」）；
  • twos |= ones & num：记录至目前元素num，二进制某位出现次 （当某位出现次时，且）；
  • threes = ones & twos：记录至目前元素num，二进制某位出现次（即当和对应位同时为时）。
  • one &= ~threes, two &= ~threes：将,中出现了次的对应位清零，实现「不考虑进位的三进制加法」。
• 复杂度分析：
  • 时间复杂度：遍历一遍 nums 需要线性时间复杂度；
  • 空间复杂度：使用常数额外空间。

代码：
python

class Solution:
    def singleNumber(self, nums: [int]) -> int:
        ones, twos, threes = 0, 0, 0
        for num in nums:
            twos |= ones & num # 二进制某位出现1次时twos = 0，出现2, 3次时twos = 1；
            ones ^= num  # 二进制某位出现2次时ones = 0，出现1, 3次时ones = 1；
            threes = ones & twos # 二进制某位出现3次时（即twos = ones = 1时）three = 1，其余即出现1, 2次时three = 0；
            ones &= ~threes # 将二进制下出现3次的位置零，实现`三进制下不考虑进位的加法`；
            twos &= ~threes
        return ones

java

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0, threes = 0;
        for(int num : nums){
            twos |= ones & num;
            ones ^= num;
            threes = ones & twos;
            ones &= ~threes;
            twos &= ~threes;
        }
        return ones;
    }
}

进一步简化

• 以上过程本质上是通过构建个变量的状态转换表来表示对应位的出现次数：使所有数字“相加”后出现次的位，出现，次的位为。由于其实是ones & twos的结果，因此我们可以舍弃，仅使用和来记录出现次数。

• 代码分析：
  • ones = ones ^ num & ~twos:
    • 当时，只当时将置，代表出现次；其余置，根据值分别代表出现次和次；
    • 当时，不变；
  • twos = twos ^ num & ~ones：
    • 当时，只当时将置，代表出现次；其余置，根据值分别代表出现次和次；
    • 当时，不变；

代码：
python

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

java

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}