学步园

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?

思路

1 如果不需要线性的时间，可以依次查询每个，和剩余的对比；总共用时（On2)

2 如果必须线性，就要考虑从更加底层的方面，比如位来考虑。可以想到出现过2次的数字，异或后，结果为0。那么所有数字异或后，只有出现一次那个仍然生存。

3 记得给ans先初始化再使用。

代码

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