Single Number (Bit Manipulation)

题目描述

给你一个数组，除了x,数组中每个元素出现2次,让你求解出这个x。
[leetcode136]https://leetcode.com/problems/single-number/

思路

1. 使用hashMap是非常容易理解并求解的不再累述。
2. 接下来就是我们的位操作，这一类题的一个通用的解法。

算法步骤

对这个数组的每一位进行异或，最后的结果就是那个单数来的数。

算法原理

异或操作满足：a^b=ba,a^a=0,0a=a
所以一趟异或操作之后，那些出现偶数次的数对结果的贡献就没有影响，这些所有的出现偶数次的数异或之后为0，而0与那个单独出现的数x异或之后就为x。

算法代码

public class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i:nums)
            res^=i;
        return res;
    }
}

算法原理很简单，实现也很简单。但这里需要注意的是，那些出现多次的必须是出现偶数次，不然这个算法就失效了，那么对于出现奇数次的怎么办呢？接下来拓展详细描述这一类题目的解法。

拓展一

[leetcode]https://leetcode.com/problems/single-number-ii/
这次数组中除了x外，每个元素出现3次，需要你找出x。注意到次数3为奇数了，上述方法失效。

思路

1. 当然了也可以使用一个hash,类似于上题的hash解法，不用改动代码即可实现。当然了，这种解法很low。不在详述。

public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(!hashMap.containsKey(nums[i]))
                hashMap.put(nums[i],1);
            else
                hashMap.put(nums[i],2);
        }
        for(int i=0;i<nums.length;i++){
            if(hashMap.get(nums[i])==1)
                return nums[i];
        }
        return -1;
    }
}

2. 使用位操作
   接下来介绍三种使用位操作的方法，其实他们的本质是一样的。

位操作方法一

算法步骤

1. 因为int是32位，所以我们考虑使用一个长度为32的数组，初始化为0。
2. 记res为最后的结果，由于res也为32位的int，我们只需要确定，res的每一位为1还是0即可，所以这里使用了一个外层32次的循环，内层函数每执行一次，确定了res的一个比特位。
3. 假设现在需要确定res的第i比特位，内层函数找出原数组中在第i比特位上为1的数，统计这些数的个数，然后对3取模，结果要么是0，要么是1(因为本题中那个特殊的数只出现一次)这个结果就是我们的res的第i比特位的值。
4. 32趟走完时候我们可以确定res的每一个比特位是0还是是1，也就可以确定res的值了。

算法原理

因为原数组中除了数res外，每个数都出现三次，所以我考察这些数的对应比特位。那些出现三次的数，对应为1的比特位相加后为3的倍数，只有这个只出现1次的数的那些为1的bit位，这些位数上count为3n+1，所以我们相加取模时候就可以确定哪些比特位为1。
比如[1,2,2,2,3,3,3]

 num      a  b
  1    ->  0   1
  2    ->  1   0
  3    ->  1   1

2和3都出现了三次，所以我们把对应比特位1的个数相加的话a比特位一共6个1，b比特位一共4个1,对3取模后a比特为0，b比特位1。我们就知道结果为0。

算法代码

public class Solution {
    public int singleNumber(int[] nums) {
        int[] count=new int[32];
        int res=0;
        for(int i=0;i<32;i++){
            for(int j=0;j<nums.length;j++){
                if(((nums[j]>>i)&1)==1)
                    count[i]++;
            }
            res|=((count[i]%3)<<i);
        }
        return res;
    }
}
//当然，一般化，假如出现多次的数出现次数为k，只需要模k即可。
//另外，如果那个特殊的数不是出现1次，
//修改res|=((count[i]%3)<<i)即可，
//例如假如出现2次，
//只需要修改为res|=((count[i]%3==0?0:1)<<i)

位操作方法二

算法步骤

1. 使用三个变量，ones twos xthree，如果二进制表示中，某个数位上"1"出现一次，那么ones在这个数位上就是"1"，同理twos表示出现两次。
2. 看看ones twos 的变化规则。新进来一个数nums[i]，考察ones&nums[i],如果ones在这个比特位上为1，表面之前这个比特位"1"出现过一次，现在nums[i]在这个比特位上又为1，那么自然就是出现了两次"1"，所以twos在这个比特位上就应该为1。ones的变化规则很简单，异或就行了。需要注意的是如果某个比特位在ones和twos中都为1,那么就代表出现了三次，需要把这个比特位清零。
3. 遍历结束后，ones就是出现一次的数，twos就是出现两次的数。

算法原理

从比特位来考虑，出现三次的数在遍历结束之后对ones和twos都没有影响，因为他们最后会在他们比特位表示为"1"的位置上出现三次，他们的影响被代码

xthree = ~(ones & twos);
            ones&=xthree;
            twos&=xthree;

抹去，最后ones的各个比特位就是只出现一次的那个数的比特位，twos的各个比特位就是只出现两次的那个数的比特位。

算法代码

public class Solution {
    public int singleNumber(int[] nums) {
        //2,2,3,2
        int ones=0;//二进制表示中“1”出现一次的数位
        int twos=0;//二进制表示中“1”出现两次的数位
        int xthree=0;
        for(int i=0;i<nums.length;i++){
            twos|=(ones&nums[i]);//出现两次，当然是“之前”位置上首先就是“1”（ones），然后输入的数树在这个位置上又是“1”
            ones^=nums[i];//出现一次，当然是异或就行了，这样出现一次的变为0，出现0次的变为1
            xthree = ~(ones & twos);//一个数位在ones和twos同时为1，表示当前数位出现了3次，应该把这个数位变为0
            ones&=xthree;
            twos&=xthree;
        }
        return ones;
    }
}
//拓展，two最终记录的是出先两次的
//http://www.cnblogs.com/daijinqiao/p/3352893.html
//[1,2,2,2,3,3,4,4,4,5,5,5]
//[1,2,2,3,3,3,4,4,4,5,5,5]

位操作方法三

这个方法其实和方法二一样，只不过搞得有点像数电设计中的状态转移。

算法步骤&原理

a表示32位的int，a的每一位怎么确定，在遍历原数组过程中，考察原数组中数的比特位表示，如果该位上"1" 出现次数为2，那么该位就为1，否则为0
同理
a表示32位的int，b的每一位怎么确定，在遍历原数组过程中，考察原数组中数的比特位表示，如果该位上"1" 出现次数为1，那么该位就为1，否则为0
那么我们很容易得到下面的状态转移表
(ai为a的i比特位，bi为b的i比特位,ci为新遍历到的数的i比特位)

 ai    bi    ci     ai’   bi'
 0     0     0      0     0
 0     1     0      0     1
 1     0     0      1     0
 0     0     1      0     1
 0     1     1      1     0
 1     0     1      0     0

我们需要找到出现次数为1的比特位，也就是bi'为1
顺便找到出现次数为2的比特位，也就是ai'为1
所以ai'=ai_bici|~aibici
bi'=_aibici|_aibici
我们就可以确定出现次数为1的比特位，也就可以确定出现次数为1的数。
这里的代码是同时找了次数为1的和为2的（这种理解是特殊的数出现一次或两次，二者选其一）

算法代码

public class Solution {
    public int singleNumber(int[] nums) {
        int a=0;
        int b=0;
        for(int c:nums){
            int tmpa=a&(~b)&(~c)|((~a)&b&c);
            b=(~a&~b&c)|(~a&b&~c);
            a=tmpa;
        }
        return a|b;
    }
}

当然，如果了解转台转移化简的话,可以简化为

 for(int c:nums){
            int tmpa=a&(~c)|(b&c);
            b=(~a&~b&c)|(b&~c);
            a=tmpa;
        }

拓展二

[leetcode260]https://leetcode.com/problems/single-number-iii/
这次是数组中有两个不同的数都只出现过一次，其他数都出现两次，让找出这两个数。

算法描述

1. 对这些数进行异或操作得到ones
2. 移位与操作得到once的比特位表示的第一个非“0”位置，并把一个数赋值为仅该位置为1，其他位置为0
3. 用这个数去和数组中的数做与运算，根据与运算结果是否为0可以把原数组中的数分为两个阵营，分别对两个阵营进行异或操作，最终得到的两个结果就是所求的两个数。

算法原理

有两个数a,b只出现一次，其他两次，那么所有数进行异或之后的结果ones，ones比特位表示为1的位置肯定就是a和b在这个位置为一个1一个0，那么就可以使用这个位置把a和b分到不同的阵营中，两个阵营都是包含a/b和一堆成对出现的数，对他们进行异或操作即可求出a/b。

算法代码

public class Solution {
  public int[] singleNumber(int[] nums) {
      int one=0;
      for(int i:nums)
          one^=i;
      int tmp=1;
      while((one&1)!=1){
          one>>=1;
          tmp<<=1;
      }
      int res1=0;
      int res2=0;
      for(int i:nums){
          if((i&tmp)==0){
              res1^=i;
          }
          else
              res2^=i;
      }
      int[] res=new int[2];
      res[0]=res1;
      res[1]=res2;
      return res;
  }
}

当然了，继续拓展的话，如果有两个数出现1次，其他书出现三次，那么就是拓展一中的方法先找到为出现次数为1的两个数共同影响产生的结果ones,然后找到一个为“1”的比特位，然后分阵营，就变为两个拓展一类型的问题。
如果一个一次一个两次其他三次，那么一次的就是ones,两次的就是twos。