[Binary Search]99클럽 코테 스터디 27일차 TIL + 0268-missing-number

268. Missing Number

Easy

---

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

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.

 

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

 

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

 

 

 

<내코드>

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()

        for index, num in enumerate(nums):
            if index != num:
                return index

        return n

 

- 어제 배웠던 enumerate로 index를 바로 뽑아낸 점에서 뿌듯했음

=> 내것이 되었다는 의미임

 

- sort() 는 O(nlogn) 이여서 부족함! 문제의 요청은 O(n) 임

=> 그런데 이분탐색으로 접근을 해도 근차이는없고 수학적인 '가우스 합공식'이 오히려 유용함

 

 

- 처음으로 캡쳐해서 직접 문제의 접근방법을 고민한방법에서 나름 참신한 방법으로 파악이 됨

<모범사례>

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

- 예상값과 실제값의 차에서 어떤값이 비었는지 파악이 가능한 O(n)의 매우 간단한 방식임

 

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num  # XOR 연산을 통해 누락된 숫자를 찾음
        return missing

- XOR은 배타적 논리합이라 함

=> 두개의 값이 같을 때 0/ 다를 때 그 값 자체

 

=> 아직 이해안됨 나중에 파악하자

 

<보충학습>

1. 이진탐색 스스로 구현

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right)//2 

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
    return -1

- 오랜만에 수도만 보고 직접 구현함