【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各项分别是：

0	1	2	3	4
c XOR a XOR a = c	c XOR b XOR a XOR b = c XOR a	c XOR b XOR a	c XOR b	b

代码：

class Solution {

public:

    int singleNumber(int A[], int n) {

        while(--n){

                A[n-] ^= A[n];

            }

            return A[];

    }

};

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

Java版本代码：

 public class Solution {

     public int singleNumber(int[] A) {

         int answer = 0;

         for(int i = 0;i < A.length;i++){

             answer = answer ^ A[i];

         }

         return answer;

     }

 }