[리트코드 (LeetCode)] Missing Number (Python)

Missing Number

• https://leetcode.com/explore/featured/card/top-interview-questions-easy/99/others/722/
• 분류: Top Interview Questions - Easy - Others

Explore - LeetCode

문제

• 주어진 배열 nums는 [0, n] 범위에 있는 n개의 서로 다른 숫자들로 구성되어 있다. 주어진 범위의 숫자 중 유일하게 배열에 없는 숫자를 찾아 반환하라.
• type nums: List[int] / rtype: int

예시

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 
             2 is the missing number in the range since it does not appear in nums.

Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 
             2 is the missing number in the range since it does not appear in nums.

Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 
             8 is the missing number in the range since it does not appear in nums.

조건

• n == nums.length
• 1 ≤ n ≤ 10^4
• 0 ≤ nums[i] ≤ n
• 배열 nums의 모든 원소는 유일함(unique)

Follow up

• O(1)의 extra space와 O(n) runtime complexity를 가진 solution을 생각해낼 수 있는가? → sum, xor 활용

풀이

1. 크기가 n+1인 check 배열을 만들고 각 배열의 원소를 순회하며 있는 원소를 true로 바꾼 후 false인 원소 인덱스 리턴하기

check = [False] * (len(nums)+1)
for num in nums: # O(n)
    check[num] = True
return check.index(False) # O(n)

Time: O(n) / Space: O(n)
Runtime: 91 ms (beats 94.97%) / Memory Usage: 14.8 MB (48.79%)

 

2-1. 0~n까지의 원소를 담은 set을 만들고 배열을 순회하면서 set에 없는 원소 찾기

number = set([i for i in range(len(nums)+1)])
for num in nums: # O(n)
    if num in number: # O(1)
        number.remove(num)
return number.pop()

Time: O(n) / Space: O(n)
Runtime: 107 ms (beats 50.99%) / Memory Usage: 15.6 MB

 

2-2. 2-1의 반대 → nums를 set으로 변환한 후 0~n에 대해 순회하며 nums에 없는 원소 반환

nums = set(nums)
for i in range(len(nums)+1):
    if i not in nums:
        return i

Time: O(n) / Space: O(n)
Runtime: 97 ms (beats 80.48%) / Memory Usage: 15.3 MB (beats 12.84%)

 

3. sort한 후 앞에서부터 순회하여 직전 수보다 1만큼 크지 않은 경우 (연속하게 증가하지 않는 경우) 리턴

nums.sort()
if nums[0] != 0:
    return 0
prev = nums[0]
for i in range(1, len(nums)):
    if nums[i] != (prev+1):
        return prev+1
    prev = nums[i]
return prev+1

Time: O(nlogn) / Space: O(1)
Runtime: 110 ms (beats 45.38%) / Memory Usage: 14.6 MB (beats 91.16%)

 

4. sum 함수를 이용 → 0~n까지의 합 - nums의 합 = 없는 원소

n = len(nums)
return n*(n+1)/2 - sum(nums)

Time: O(n) / Space: O(1)
Runtime: 94 ms (beats 89.25%) / Memory Usage: 14.6 MB (beats 71.28%)

 

5. 차집합 연산 이용 - 0~n까지의 원소가 담긴 집합과 nums 집합의 차집합에 있는 원소가 찾는 원소

return (set(range(len(nums)+1) - set(nums)).pop()

Time: O(n) / Space: O(n)
Runtime: 95 ms (beats 87.16%) / Memory Usage: 15.5 MB (beats 7.3%)

 

6. XOR 연산 활용

• 출처: [Python] THE Best explanation, bitwise and sum

Explore - LeetCode

 

1) xor 연산은 두 피연산자가 서로 다를 때만 True (같으면 False, 즉 0)

1^0 = 1 , 1^1 = 0 , 2^0 = 2 , 2^2 = 0

2) xor 연산은 교환 법칙이 성립함 → 연산의 순서와 무관하게 같은 두 수가 있으면 그 두 수의 연산 결과는 0이 됨

3^5^6^3^6^5 == (3^3) ^ (5^5) ^ (6^6) == 0

 

→ 0~n의 수와 nums의 원소에 대해 xor연산을 실행하면 missing element만 결과변수에 남을 것

def missingNumber(self, nums):
    result = 0
    for counter,value in enumerate(nums):
        result ^= counter+1 # XOR result with numbers from the complete series
        result ^= value # XOR with the numbers given in num series
    return result

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

Runtime: 98 ms (beats 76.3%) / Memory Usage: 14.9 MB (beats 27.73%)

 

부연 설명

# Simple break down of above XOR solution
numsList = [3,0,1] # Missing number is 2
result = 0 

#XOR result with complete number sequence
for number in range(len(numsList) + 1 ) : # 0, 1, 2 ,3
		result ^= number
		
# Essentially now result = ( 0 ^ 0 ^ 1 ^ 2 ^ 3)

#XOR result with values in nums
for num in numsList : # 3,0,1
		result ^= num
		
# result = ( 0 ^ 0 ^ 1 ^ 2 ^ 3) ^ ( 3 ^ 0 ^ 1)

# XOR of same values cancel each other out 

# result = (0) ^ (0 ^ 0)  ^ (1^1) ^ (2) ^ (3^3)
# result =  0 ^ 0 ^ 0 ^ 2 ^ 0
# result = 2

return result # 2