首页 > 代码库 > 【LeetCode】Single Number

【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?


      思路:

      为了满足时间和空间复杂度,必须利用异或的性质。

      异或: 1 XOR 1 = 0     0 XOR 0 = 0     1 XOR 0 = 1    0 XOR 1 = 1      即相同为 0,不同为1

      根据异或性质,有如下等式: 对任意整数,a b c ,  a XOR a = 0    a XOR b XOR a = b

      即任意两个相同的数异或一定得 0, 若是一堆数,除了一个数,其他都是成对出现,则将所有数异或起来,剩下的就是我们要找的数。复杂度为 O(n)


      代码:

class Solution{
public:
    int singleNumber(int A[], int n) {
        int ans;
        for(int i = 0; i < n;++i)
            ans ^= A[i];
        return ans;
    }
};

【LeetCode】Single Number