645. Set Mismatch

Description

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

• 2 <= nums.length <= 10⁴
• 1 <= nums[i] <= 10⁴

Submitted Code

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        count = {}
        expected_sum = len(nums) * (len(nums)+1) // 2   # 1부터 n까지의 합
        actual_sum = 0                                  # 실제 nums의 원소 합
        
        for num in nums:
            actual_sum += num
            count[num] = count.get(num, 0) + 1          # num의 등장 횟수 카운트
            if count[num] == 2:
                # 중복 등장한 숫자
                duplicated_num = num

        # 빠진 숫자 계산
        missing_num = expected_sum - (actual_sum - duplicated_num)
        return [duplicated_num, missing_num]

Runtime: 15 ms | Beats 59.40%
Memory: 14.23 MB | Beats 20.36%

중복 등장하는 숫자는 해시맵을 이용하여 알아내고 빠진 숫자는 모든 원소의 합을 통해 계산했다.

Other Solutions

1st

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n, a, b = len(nums), sum(nums), sum(set(nums))
        s = n*(n+1)//2
        
        return [a-b, s-b]

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)

set()을 이용해서 1부터 n의 합에서 중복된 숫자 하나만 빠진 값(위의 코드에서 actual_sum - duplicated_num 부분)을 간단하게 구할 수 있다.

2nd

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:

        miss_xor_rep = 0
        
        for i in range(len(nums)):          # nums의 모든 원소 XOR
            miss_xor_rep ^= nums[i]
        
        for i in range(1,len(nums)+1):      # 1부터 n까지 XOR → (중복수 ^ 빠진수)가 남음
            miss_xor_rep ^= i
        
        # 가장 마지막(오른쪽) 1비트 추출(중복수와 빠진수의 서로 다른 비트 위치)
        rightmost_set_bit = (((miss_xor_rep-1)^(miss_xor_rep)) & miss_xor_rep)
        
        # rightmost_set_bit를 기준으로 그룹 나누기(num1은 비트가 1, num2는 0인 그룹)
        num1, num2 = 0,0
        for i in range(len(nums)):          # nums의 모든 원소 XOR
            if rightmost_set_bit & nums[i]:
                num1 ^= nums[i]
            else:
                num2 ^= nums[i]
        
        for i in range(1,len(nums)+1):      # 1부터 n까지 XOR
            if i & rightmost_set_bit:
                num1 ^= i
            else:
                num2 ^= i    
        
        # 둘 중 실제로 nums에 있는 수가 중복수, 나머지가 빠진수
        if num1 in nums:
            return [num1, num2]
        else:
            return [num2, num1]

XOR 비트마스크 방법을 사용하면 공간 복잡도를 𝑂(1)으로 줄일 수 있다.