Leetcode136

Leetcode136：只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

解法一：基于map的统计方法

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> mp;
        for (int i = 0; i<nums.size(); i++)
            mp[nums[i]]++;
        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++)
        {
            if (it->second<2)
            {
                return it->first;
                break;

            }
        }
        return it->first;
    }
};

解法二：基于sort的排序方法

class Solution2 {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int j = 1, i = 0;
        for (i = 0; i<nums.size();)
        {
            if (j == nums.size())
                return nums[j - 1];
            else if (nums[i] == nums[j])
            {
                i += 2;
                j += 2;
            }
            else
            {
                return nums[i];
                break;
            }
        }
        return nums[i];
    }
};

解法三：基于异或的方法

/***************************************************************************************
基于异或的方法
这是这个题的最优解法，也是看过题解后发现的最好的一种解法，异或运算有下面的几个特点：

一个数和 0 做 XOR 运算等于本身： a⊕0 = a
一个数和其本身做 XOR 运算等于 0： a⊕a = 0
XOR 运算满足交换律和结合律： a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

所以，这个题只需要遍历一遍数组，把所有的元素进行一次异或运算，就可以得到最后的答案，时间复杂度O(n)， 
空间复杂度O(n) 不需要开辟额外的空间
****************************************************************************************/
class Solution3 {
public:
    int singleNumber(vector<int>& nums) {
        int len = nums.size();

        int res = 0;
        for (int i = 0; i<len; i++)
            res ^= nums[i];
        return res;
    }
};