【leetcode刷题笔记】Single Number

题目：

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?

看了别人的解答才会的，利用公式a XOR b XOR a = b,从A[n]开始，依次往前执行A[n] = A[n] XOR A[n-1],最后A[0]就是答案。

例如如果序列是｛a,b,a,c,b｝

那么数组A各项分别是：

代码：

class Solution {
public:
    int singleNumber(int A[], int n) {
        while(--n){
                A[n-1] ^= A[n];
            }
            return A[0];
    }
};

这里自己还犯了一个白痴想法，认为a XOR b要么是0要么是1，这个只是对于a，b为0，1的时候成立的，如果a，b不是0，1，此时是把a，b表示成二进制数后逐位异或的。

【leetcode刷题笔记】Single Number,布布扣,bubuko.com

【leetcode刷题笔记】Single Number

原文：http://www.cnblogs.com/sunshineatnoon/p/3636727.html