LeetCode | 位运算巧解01.10--01.11

• LeetCode 136.Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
思路：巧妙的异或计算题，将所给的数组中的每一个数字都异或起来，由于异或相同为0，不同为1，且任何数与0异或为其本身，故可通过此方法快速找到只出现一次的那个数。

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

• LeetCode137.Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
思路：本题是上一题的变种，有一个数字只出现了一次而其他的数字均出现了三次。通过建立一个32位的数字，来统计每一位上1出现的个数，我们知道如果某一位上为1的话，那么如果该整数出现了三次，对3取余为0，我们只需要把每个数的对应位都加起来对3取余，最终剩下来的那个数就是单独的数字。 复杂度：O(32*N)，这是一个通用的解法，如果把出现3次改为 k 次，那么只需模k就行了。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int i = 0; i < 32; i++){
            int count = 0;
            for(int j = 0; j < nums.length; j++){
                count += nums[j]>>i&1;
            }
            result += count%3<<i;
        }
        return result;
    }
}

• LeetCode260.Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
Example:
Input: [1,2,1,3,2,5]
Output: [3,5]
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
思路：首先对原数组进行异或运算，结果是一个数字，这个数字是数组中两个不相同的数字异或的结果。我们取出其中任意一位为‘1’的位，为了方便起见，我们用 a &= -a 来取出最右端为‘1’的位，具体来说下这个是如何操作的吧。就拿题目中的例子来说，如果我们将其全部亦或起来，就剩3和5亦或起来，那么就是二进制的11和101亦或，得到结果110。然后我们进行 temp &= -temp 操作。首先变负数吧，在二进制中负数采用补码的形式，而补码就是反码+1，那么110的反码是 11...1001，那么加1后是 11...1010，然后和 110 相与，得到了10，就是代码中的temp变量。得到了这个temp ，就可以将原数组分为两个数组了。为什么呢，如果两个相同的数字亦或，每位都会是0，而不同的数字亦或，一定会有对应位不同，一个0一个1，这样亦或是1。比如3和5的二进制11和101，如果从低往高看，最开始产生不同的就是第二位，那么我们用第二位来和数组中每个数字相与，根据结果的不同，一定可以把3和5区分开来，而其他的数字由于是成对出现，所以区分开来也是成对的，最终都会亦或成0，不会3和5产生影响。分别将两个小组中的数字都异或起来，就可以得到最终结果了

class Solution {
    public int[] singleNumber(int[] nums) {
        int result[] = new int[2];
        int temp = 0;
        for(int i = 0; i < nums.length; i++){
            temp^=nums[i];
        }
        temp &=-temp;
        for(int i = 0; i < nums.length; i++){ 
            if((temp&nums[i]) != 0){
                result[0] ^= nums[i];
            }else{
                result[1] ^= nums[i];
            }
        }
        return result;
    }
}