136.Single Number

Tags: Eeasy Bit Manipulation

Links: https://leetcode.com/problems/single-number/

---

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

---

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        map<int, int> store;

        for (size_t i = 0; i < nums.size(); ++i){
            ++store[nums[i]];
        }

        for (auto e : store){
            if (e.second == 1){
                result = e.first;
                break;
            }
        }

        return result;
    }
};

这是一种很常规的思路，但是题目要求不能使用额外空间，显然此方法不满足。

不使用额外空间很容易联想到不使用额外空间交换两个变量的值：

int a = 3, b = 4;
a =  a ^ b;
b = a ^ b;
a = a ^ b;

所以考虑采用位运算里的异或性质来解决。

题目限定每个数除了特殊的一个只出现一次，其他的都会出现两次，两个相同的数异或为0，那么最后留下的必然是只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (auto e : nums)
            result ^= e;

        return result;
    }
};