Single Number I

XOR => 异或

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

        return res;
    }
}

Single Number II

Create an array with size 32, if a number appears three times, then the every bit should be divided evenly by 3

Mistakes

bit manipulation should be enclosed by parentheses

• (nums[j] & mask) != 0

How to set bit?!!!!!

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) return -1;

        int res = 0;
        int[] bits = new int[32];

        for (int i = 0; i < bits.length; ++i) {
            int mask = 1 << i;
            for (int j = 0; j < nums.length; ++j) {
                if ((nums[j] & mask) != 0) bits[i]++;
                bits[i] %= 3;
            }

            res |= bits[i] << i;
        }

        return res;
    }
}

Single Number III

divide the input array into two groups, each group only has one single number

• the first pass, XOR all the elements, and the result would be the XOR of the two numbers we need to find.
• since this two numbers must be different, find the first bit that they are different and divide the input array by whether or not that bit is 1

then do XOR of each group

Mistakes

can I do the divide and XOR at the same time in order to reduce space use

public class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for (int num : nums) {
            diff ^= num;
        }
        //get the lowest 1 bit
        diff &= ~(diff - 1);

        int[] res = {0, 0};
        for (int num : nums) {
            if ((num & diff) != 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }

        return res;
    }
}