题目链接：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次以外其余每个元素都出现2次，找到只出现1次的元素。

  1. Hash

可以采用Hash表记录每个出现的元素，最后输出只出现1次的即可。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int singleNumber(int A[], int n)
    {
        unordered_map<int, int> m;
        for(int i = 0 ; i < n; ++ i)
            ++ m[A[i]];
        for(auto it = m.begin(); it != m.end(); ++ it)
            if(it -> second == 1)
                return it -> first;
        return 0;
    }
};

或者用set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution
{
public:
    int singleNumber(int A[], int n)
    {
        unordered_set<int> s;
        for(int i = 0 ; i < n; ++ i)
        {
            if(s.find(A[i]) != s.end())
                s.erase(A[i]);
            else
                s.insert(A[i]);
        }
        return *(s.begin());
    }
};

  1. 异或操作

由于Hash的方式需要O(n)的空间复杂度，而题目要求不使用额外空间，因此还需要令求它解。

先说一下异或操作，一个数异或它本身，结果是0；一个数与0异或，结果是它本身；而且异或还满足交换律。因此，可以考虑用异或将出现两次的数字去掉，那么，剩下的就是只出现1次的数字了。也就是说，返回数组中所有数字异或的结果即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10

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