(Leet Code c++)Single Number

136. Single Number

 

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

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 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

map 자료구조를 이용하여 문제 해결.

 

for문을 통해 nums의 원소가 나타난 횟수를 map<int, int> m에 저장한다.

마지막에는 m을 순회하면서 맵에 저장된 원소가 나온 횟수가 저장되어 있는 두번째 값(second)이 1이면 answer에 저장 후 break 하여 리턴하면 된다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> m;
        int answer = 0;
        
        for(int i = 0; i < nums.size(); i++){
            m[nums[i]]++;
        }
        
        for(auto itr = m.begin(); itr != m.end(); itr++){
            if(itr->second == 1){
                answer = itr->first;
                break;
            }
        }
        
        return answer;
    }
};