136 Single Number

• 题目描述：
  给一个整型数组，除了一个整数只出现一次，其他所有整数均出现两次，找出给唯一出现一次的数

• 分析：
  位运算，利用位运算的性质做题，出现过两次基本上代表了异或结果为0，数组所有元素异或最终结果就是目标元素

public class Solution {
    public int singleNumber(int[] nums) {
        int i = nums[0];
        for(int k = 1; k < nums.length;k++)
        {
            i ^= nums[k];
        }
        return i;
    }
}

• 扩展

  • Single Number II：除一个元素出现一次之外，其他元素均出现三次，求该唯一元素
  • Single Number III：除两个元素出现一次之外，其他元素均出现过两次，求这两个元素

// Single Number II
// 位运算，int为32位bit，在每个数的32位表示中，要么1要么0，因此对于某一位上出现的0或1的个数应该是3个倍数（在不考虑目标元素的条件下）。
// 因此对每一位上计算的1或0的个数之和求模3即为目标元素在该位上的值（1/0），32个位依次计算，时间O(N)
public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0; 
        int len = nums.length;
        for(int i = 0; i < 32;i++){
            int sum = 0;
            for(int j = 0; j < len; j++){
                sum += (nums[j] >> i) & 1;
            }
            result |= (sum % 3) << i;
        }
        return result;
    }
}

// Single Number III
// 位运算，类同第一个问题，异或后找到的是目标两元素X,Y的异或值A，在A中32位中1代表该位上X,Y是不一样的
// 由此，将数组以该位1/0分为两组，因为成对出现的数必定同在一组，因此问题退化为问题一，在两组中分别求解目标元素
public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] ret = new int[2];
        int i,j;
        int[] num1 = new int[nums.length];
        int[] num2 = new int[nums.length];
        int tmp = nums[0];
        for(int k= 1; k< nums.length;k++){
            tmp ^= nums[k];
        }
        int position = 0;
        while(tmp%2==0){
            tmp /= 2;
            position++;
        }
        int length1=0,length2=0;
        for(int k= 0,m=0,n=0; k < nums.length;k++){
            if((nums[k]>>position)%2!=0){
                num1[m] = nums[k];
                m++;
                length1 = m;
            }
            else {
                num2[n] = nums[k];
                n++;
                length2 = n;
            }
        }
        ret[0] = num1[0];
        ret[1] = num2[0];
        for(int k = 1; k < length1;k++)
        {
            ret[0] ^= num1[k];
        }
        for(int k = 1; k < length2;k++)
        {
            ret[1] ^= num2[k];
        }
        return ret;
    }
}