[LeetCode Road] Single Number - Solution/C++

Question:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example:

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

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

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10^4

-3 * 10^4 <= nums[i] <= 3 * 10^4

Each element in the array appears twice except for one element which appears only once.

Source code

Version 1

Idea:
I need a pool to store elements, those are recorded by a counter. Hence, I remember one of LeetCode question I had done before. The question of Two Sum solution is map. A map container is supporting generic type key-value pairs with the templates.

Therefore, the elements of nums vector will be stored into map<int,int>, I set the element as a key (unique), give 1 as a value (means a counter). If the element is exist in map already, a counter will be added 1.

Finally, I use a loop to check each pairs whether a counter is equal to 1. Remember to return a key of pair.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        map<int, int> mapNum;
        map<int, int>::iterator it;
        int ans;
        for(int i = 0; i < nums.size(); i++){
            it = mapNum.find(nums[i]);
            if(it == mapNum.end()){
                mapNum.insert(pair<int,int>(nums[i], 1));
            }else{
                it->second += 1;
            }
        } 
        for(it = mapNum.begin(); it != mapNum.end(); it++){
            if(it->second == 1){
                ans = it->first;
                break;
            }
        }
        return ans;
    }
};

Version 2

Idea:
This is an optimal algorithm that refered to internet. A Logical operator is very impressive method to solve it.

Exclusive or (XOR) is one of a logicl operator that outputs is true (=1) only when two inputs differ. On the contrary, outputs is false (=0) only when the two inputs are the same.

E.g.,
   1 0
XOR 1 0
   0 0

Hence, we can do XOR for each elements and the result appears only once.

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i++){
            res ^= nums[i];
        }
        return res;
    }
};