Single Number II

Single Number II

 

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Naive Way:根据Single Number 中的做法，有没有一种运算x 能使得
1 x 1 x 1 = 0;
0 x 0 x 0 = 0;
1 x 0 = 1;
0 x 0 = 0;

要是有也不是一种好办法，因为如果k=4,5,6...就还要想新的运算。所以必须有一种运算能够满足k个的情况。

以上推断给了一个实例，如果k个数，在同一个 bit 位上就可能会有 k 个 1，如果用一个 int 表示每一位上 1 的个数，有k个数的就会有k个1，最后除以k就会被除尽，而多出的那个1就是多出的那个 single one 的对应 bit 位上的 1。

算法复杂度 O(n), space O(1)

 public class Solution {  
   public int singleNumber(int[] A) {  
     int k = 3;  
     int x = 0;  
     int num[] = new int[32];  
     for(int i = 0;i < A.length;i++)  
       for(int j = 0;j < num.length;j++)  
         num[j] += ((A[i] & (1 << j)) != 0)?1:0;  
     for(int j = 0;j < num.length;j++) x |= ((num[j]%k) << j);  
     return x;  
   }  
 }  

Improved Way:此题在Discuss里的方法还真不少。

  public class Solution {  
   public int singleNumber(int[] A) {  
     int ones = 0, twos = 0;  
     for(int i = 0; i < A.length; i++){  
       ones = (ones ^ A[i]) & ~twos;  
       twos = (twos ^ A[i]) & ~ones;  
     }  
     return ones;  
   }  
 }  

这里有一个方法找到了一种 x 运算满足之前说的条件。

来自leetcode 用户  againest1 。理解这个算法首先要认识到数字出现的顺序对于比特运算是无关的，根据比特运算的交换律。那么我们可以把这个序列看成是连续三个一样的不停出现，直到那一个落单的。
第一个 x 出现，ones = x & ~0 = x, twos = x & ~x = 0;
第二个 x 出现，ones = x ^ x & ~0 = 0 & ~0 = 0; twos = 0 ^ x & ~0 = x;
第三个 x 出现，ones = 0 ^ x & ~x = x & ~x = 0; twos = x ^ x & ~0 = 0;
只出现一次会被ones记录，只出现两次会被twos记录，出现3次两者都不记录。


 这里还有一个解释超长的，做法是一样的 https://oj.leetcode.com/discuss/9763/accepted-proper-explaination-does-anyone-have-better-idea