[LeetCode] 136. Single Number

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 1:
Input: nums = [2,2,1]
Output: 1

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

Example 3:
Input: nums = [1]
Output: 1

Constraints:

1<= num.length <= 3 * 104

-3 * 104  <=num[i]  <= 3 * 104

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

Solution.h

#include<iostream>
#include<vector>
#include<map>

class Solution
{
public:
    int singleNumber(std::vector<int>& nums);
};

 

Solution.cpp

#include "Solution.h"

int Solution::singleNumber(std::vector<int>& nums)
{
    
    /*
    time out
    std::vector<int>::iterator iter;
    int temp = 0;
    for (int loop_i = 0; loop_i < nums.size();) {
        temp = nums[loop_i];
        nums.erase(nums.begin()+loop_i);
        iter = std::find(nums.begin(), nums.end(), temp);
        if (iter == nums.end()) {
            return temp;
        }
        else{
            nums.push_back(temp);
            
        }
        return -1;
    }
    */
    std::map<int, bool> temp_map;
    std::pair<std::map<int, bool>::iterator, bool> check;
    for (int loop_i = 0; loop_i < nums.size(); loop_i++) {
        check= temp_map.insert(std::pair<int,bool>(nums[loop_i], true));
        if (check.second == false) {
            temp_map.erase(temp_map.find(nums[loop_i]));
            temp_map[nums[loop_i]] = false;
        }
       
    }
    for (auto iter = temp_map.begin(); iter != temp_map.end(); iter++) {
        if (iter->second) {
            return iter->first;
        }
    }
    return 0;
}

1. Time Out Case

배열을 통하여 데이터 조회 후 삭제를 진행하려 하였으나 시간복잡도 O(n) Time Out이 발생 되는 문제가 발생.

Data 5000개 이상 주입 등...

2.  Map 활용

시간 복잡도를 줄이기 위하여 Map을 사용하여 KEY에 중복 판단을 통하여 문제를 해결하고자 하였음.

Result :

 

GitHub : github.com/Anchangun

Anchangun - Overview