(Easy - Arrays) Leetcode - 136. Single Number

주어진 배열에서 한 쌍이 아닌, 즉 같은 숫자가 존재하지 않는 숫자를 찾는 문제입니다.

총 3가지 방식이 존재하는데 이 중 추가적인 조건인 linear runtime, 즉 시간 복잡도가 O(N)이고 추가적인 공간은 사용하지 말아야 합니다.

 

맵을 사용한 빈도수 확인 방식

 

nums 배열에 같은 숫자가 몇 개 있는지 확인하기 위해 정렬된 맵은 필요하지 않으므로 해시맵인 unordered_map을 사용했습니다. (해시맵이 key값으로 value를 찾는데 시간이 더 적게 걸립니다. Average: O(1))

그리고 빈도수를 확인해 1번만 나왔다면 그 숫자가 답이 됩니다.

이 방법은 O(N)의 시간복잡도를 가지지만 맵을 사용하기 위해 추가적인 공간이 필요해 문제의 조건을 만족할 수 없습니다.

int singleNumber(vector<int>& nums) {
    if (nums.size() < 2) 
    	return nums[0];
        
    std::unordered_map<int, int> freq;
    for (int& i : nums)
    	freq[i]++; // nums에 같은 숫자가 얼마나 있는지
    
    for (const auto& [key, value] : freq)
    	if (value == 1) // 1개라면
        	return key;
    
    return -1;
}

정렬 방식 

주어진 배열을 정렬한 후 2개씩 숫자를 비교하는 방법입니다.

정렬하는데 걸리는 시간으로 인해 시간복잡도 O(N log N)을 가지지만 추가적인 공간을 사용하지 않습니다.

Linear Time Complexity인 O(N)에 가까워 문제의 조건을 만족할 수 있을것 같습니다.

int singleNumber(vector<int>& nums) {
    if (nums.size() < 2)
        return nums[0];
	
    std::sort(nums.begin(), nums.end());
    for (int i = 1; i < num.size(); i += 2) // 숫자 2개씩 비교
    	if (nums[i - 1] != nums[i])
        	return nums[i - 1];
            
    return nums.back();
}

 

Bit 계산을 사용한 방식

하지만 XOR의 성질을 이용한 bit 계산을 하면 시간복잡도 O(N)에 constance extra space, 즉 추가적인 공간 1만 사용합니다.

XOR의 성질

     1 ^ 1 = 0

     0 ^ 1 = 1

     1 ^ 0 = 1

     0 ^ 0 = 0

즉, 같으면 0이되고 다르면 1이 됩니다. 

이 성질을 char에 사용하면 다음과 같습니다.

     A ^ A = 0

     A ^ A ^ B = B

이 방식을 활용해 nums 배열에 같은 값이 존재하면 XOR 연산으로 인해 0이 되고

같은 값이 없다면 그 숫자만 남게 될 것입니다.

int singleNumber(vector<int>& nums) {
    if (nums.size() < 2)
    	return nums[0];
        
    int ans = 0;
    for (int& i : nums)
    	ans ^= i;
    return ans;
}