137. 只出现一次的数字 II

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,3,2]
输出: 3

示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

题解

方法一：借助Map统计次数

方法二：位运算

• 统计二进制表示下，每一位出现1的次数。
• [除了某个元素只出现一次以外，其余每个元素均出现了三次]。则每一位出现1的次数%3，即可得到目标。
• 对于二进制的任意一位来说，出现1的次数%3的结果有：0、1、2。则用两个标志位即可表示，即00(0)、01(1)、10(2)。
• 当二进制的任意一位出现了为1的情况时，标志位需要更新。变换状态为：00——>01——>10——>00循环。假设两个标志位分别为：two one，则当二进制位出现1时，对于one而言：
  • two=0
    • one=0，则one变为1;one=1，则one变为0.(one=one^1)
  • two=1
    • one=0，则one变为0.（one=~two）
  • 结合上述情况，one的变化公式为：one=one^1&~two.
  • 同理，在新one的基础上，two的变化公式为：two=tow^1&~one.

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