题目描述

描述

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

注意

你需要给出一个线性时间复杂度的算法，你能在不使用额外内存空间的情况下解决这个问题么？

示例

输入： [1,0,1]

返回值： 0

题解

采用位运算中的异或运算。当两个相同的数字做异或时，结果为0。任意数字与0做异或，结果为原数字。根据异或运算的性质，此题可以采用异或运算的方式，来消除数组中出现两次的数字。

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @return int整型
     */
    int singleNumber(int* A, int n) {
        int result = 0;
        for(int i=0;i<n;i++)
        {
            result ^= A[i];
        }
        return result;
    }
};