题目描述

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

示例 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;
}
}