leetcode 136 Single Number, 260 Single Number III

leetcode 136. 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?

解题思路：

　　如果以线性复杂度和不申请额外内存的标准来衡量这道题，那么还是比较有难度的。

　　利用位运算之异或的性质来解。

代码如下：

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

View Code

leetcode 137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路：

　　利用 unordered_map 模拟 hash 表，记录元素出现过的次数 pair<number, times>

代码如下：

class Solution {
public:
    int singleNumber(const vector<int>& nums) {
        unordered_map<int, unsigned> m;
        
        for(auto e : nums)
        {
            m[e]++;
        }
        
        for(auto e : m)
        {
            if(e.second == 1)   return e.first;
        }
        
        return -1;
    }
};

View Code

leetcode 260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解题思路：

　　把所有数存入哈希表，数值大小作为 key ，该数出现的次数——value——每次累加。

　　然后再遍历哈希表，把 value == 1 的 key 取出来即是本题答案。

代码如下：

class Solution {
public:
    vector<int> singleNumber(const vector<int>& nums) {
        unordered_map<int, unsigned> m;
        
        for(auto e : nums)
        {
            m[e]++;
        }
        
        vector<int> v;
        
        for(auto e : m)
        {
            if(e.second == 1)
            {
                v.push_back(e.first);
            }
        }
        
        return v;
    }
};

View Code