SingleNumberOPT [source code]

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

    public static void main (String[] args) {
        SingleNumberOPT tester = new SingleNumberOPT();
        int[] input1 = {2,2,1,3,3};
        assert tester.singleNumber(input1) == 1 : "fail 1";
        int[] input2 = {1,2,3,5,1,3,2,6,6};
        assert tester.singleNumber(input2) == 5 : "fail 1";
        System.out.println(tester.singleNumber(input2));
    }
}

最优解是用的 xor, 这里是原理:

we use bitwise XOR to solve this problem :

first , we have to know the bitwise XOR in java

0 ^ N = N
N ^ N = 0
So..... if N is the single number

N1 ^ N1 ^ N2 ^ N2 ^..............^ Nx ^ Nx ^ N
= (N1^N1) ^ (N2^N2) ^..............^ (Nx^Nx) ^ N
= 0 ^ 0 ^ ..........^ 0 ^ N
= N

这个算法总体来说还是比较聪明的.
这里不好对付的要求是on extra space, 这个在实际的面试过程当中估计也是会碰到的, 暂时还没有想到什么很好的方法总结;

理解了核心算法, 这个问题的代码总体就很好写了. 这里这个代码是0 space, 当然也可以用1space, 就是一开始来一个int res, 然后后面遍历是0..length-1, 不过这里直接把0当做是buffer, 然后遍历的时候是1..length-1就行了.

这个题目完成的一个问题其实是有一定的普遍性的, 比如我们想要一个 array 里面所以的duplicate, 偶数个之间两两消除, 类似这里完成的就是这个操作. xor 在照 duplicate 问题当中往往可以有妙用;

这个题后来在v2上面看到一个Follow-Up: 如果要求你1pass的同时, 还要能够统计出来pair的type的数量怎么写? 其实也很简单:

int single_num = 0, type_num = 0, map count;  
for (int num : nums) {  
    single_num ^= num;  
    if (count[num]++ == 0)  
        type_num++;  
}  
if (--count[single_num] == 0)  
    type_num--;  
return (single_num, type_num);

Problem Description

Given an 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?

Hide Tags Hash Table Bit Manipulation
Hide Similar Problems (M) Single Number II (M) Single Number III (E) Missing Number (M) Find the Duplicate Number (E) Find the Difference