巧妙地利用位元算的特性可以以极低的时空复杂度解决问题

1.只出现一次的数字 I

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

思路： 位运算——数组中两两异或即可！

因为有 a ^ a = 0,0 ^ a = a ,并且异或运算满足交换律 故对数组[a,b,c,a,d,d,b] 通过异或运算: a ^ b ^ c ^ a ^ d ^ d ^ b -> a ^ a ^ b ^ b ^ d ^ d ^ c -> 0 ^ 0 ^ 0 ^ c - > c !

2. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

思路：求出每一位和，对3取余即可！

因为只有一个数字出现一次，其他都是三次，说明在每一位上，如果特殊数字出现，那么这一位上 1 的个数一定不是 3 的倍数！相反若其他数字在某位出现而特殊的没有出现，则该位上的 1 的数量一定是 3 的倍数

 public static int singleNumber (int[] A) {
        // write code here
        if(A == null || A.length == 0){
            return -1;
        }
        int res = 0;
        for(int i = 0;i < 32;i++){ //整数一共32位！所以每一位都得需要统计
            int sum = 0;
            for(int j = 0; j< A.length;j++){ 
                sum += ((A[j] >> i) & 1); //统计第 i 位上 1 的数量
            }
            res += ((sum % 3)<<i); //注意左移i过去的需要右移i回来！！！！
        }
        return res;
    }

延伸一下，对于某数组若只有一个数字出现一次，其他数字都出现 n 次 (n > 1)，则都可以通过统计每一位上 1 的数量来做！

3.只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
输入: [1,2,1,3,2,5]
输出: [3,5]

思路：结合 题目（只出现一次的数字 I） 来做

因为本题有两个数字(假设位a和b)只出现一次，其他都出现两次，所以根据题目一可以马上得到这两个特殊数字的异或结果，即为 a ^ b。之后怎么做？我们知道两数的异或结果代表了两个数字在某些位上的不同！
所以根据这个性质我们可以将该数组分成两部分，这两部分分别只有一个特殊数字！之后分别全部异或一下就得到两个特殊数字！
可以通过 a ^ b 从右开始的第一个出现的 1 所在的 位 作为区分标准！因为这个 1 代表了 a 和 b 在当前位的不同

public int[] singleNumber(int[] nums) {
        if(nums == null || nums.length <= 1){
            return new int[]{};
        }
        int xor = 0;
        for(int n : nums){
            xor ^= n; //求出两数的异或
        }
        int bit = 1;
        while((xor & 1) == 0){
            //从左往右寻找第一个 1
            xor >>=1;
            bit <<= 1;
        }
        int val1 = 0;
        int val2 = 0;
        for(int n : nums){
            if((n & bit) == 0){ //如果和当前bit位相同，则归为一类
                val1 ^= n;
            }else{ //否则归为另一类
                val2 ^= n;
            }
        }
        return new int[]{val1,val2};
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接