[C++]LeetCode: 66 Single Number

[C++]LeetCode: 66 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?

思路：

要求線性時間完成，並且不使用額外的存儲空間。

**非常之巧妙**

使用異或來排除double值，剩下的就是single one. 異或具有可交換性，順序可變。

比如給出數組{2,1,4,5,2,4,1} ，求異或，2^1^4^5^2^4^1 <=> (2^2)^(1^1)^(4^4)^(5) <=> (0)^(0)^(0)^5 = 5

AC Code:

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