[LeetCode] 287. Find the Duplicate Number [Python] 이진탐색

leetcode.com/problems/find-the-duplicate-number/

Find the Duplicate Number - LeetCode

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

1. How can we prove that at least one duplicate number must exist in nums? 
2. Can you solve the problem without modifying the array nums?
3. Can you solve the problem using only constant, O(1) extra space?
4. Can you solve the problem with runtime complexity less than O(n^2)?

 

해당 문제는 중복되는 숫자를 찾는 문제이다. Constraints에 nums에는 반드시 한 개의 숫자가 2번 혹은 그 이상 들어있다고 한다.

이 문제를 읽자마자 바로 생각난 방법은 바로 sort를 이용하여 푸는 것이었다. 

---

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i-1] == nums[i]:
                return nums[i]
        return -1

---

위의 솔루션은 inbuilt function인 sort()를 이용하여 주어진 list를 오름차순으로 정렬하고, 그 후에 for loop을 이용하여 element와 그 이전의 element가 같은 값을 가지고 있는지 비교를 한다. 이때, 같은 값을 가지고 있으면 해당 element의 value를 리턴한다. 사실, 이 문제는 constraints에 이미 '반드시' 한 개의 중복되는 숫자가 있다고 명시되어있기때문에 굳이 for loop밖에서 return을 할 필요는 없지만, 나의 c++의 코딩 습관 때문에 넣었다. 이 솔루션의 경우, extra space를 사용하지 않고 있기 때문에 space complexity는 O(1)이며 runtime complexity는 sort 의 nlogn과 for loop의 n으로, O(nlogn + n) = O(nlogn)이 된다.

 

하지만 Follow-ups를 보면, 2. Can you solve the problem without modifying the array nums? 가 적혀있다. 즉, 주어진 리스트를 변경하지 않고 이 문제를 풀 수 있느냐를 묻는 것이다. Sort()를 사용하게 될 경우, 주어진 리스트를 변경하게 되기 때문에 sort()를 이용한 솔루션은 사용하지 말고 풀어야 한다. follow ups를 읽어보면, #2는 sort() (inplace)를 사용하지 말라는 것이고 #3 은 hash map/set 혹은 sorted()를 이용하지 말라는 것을 의미한다. #4는 runtime complexity가 O(n^2) 보다 나아야 하므로 bruteforce 방법 역시 적용할 수 없다. 그 와중에 놓친 부분이 있었으니! 바로 Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. 리스트 안에 들어있는 숫자들은 1부터 n까지의 연속된 숫자들이라는 것! 

---

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low, high = 1, len(nums)-1
        
        while low <= high:
            mid = low+(high-low)//2
            c = 0
            
            for n in nums:
                if n < mid: c += 1
                
            if c < mid: low = mid+1
            else: high = mid-1
        return high

---

이 솔루션은 binary search를 이용하여 푼 것이다. 짧게 설명하자면, low와 high는 주어진 도메인 값[1, n]으로 설정했다. Binary search의 기본 템플릿에서 mid보다 작은 숫자를 셀 수 있는 for loop을 추가하였다. variable c는 mid보다 작은 숫자를 counting 하는 변수이다.  for loop이 끝난 후, low와 high의 중간값인 mid보다 c가 크다면, mid보다 작은 숫자 중에 중복되는 숫자가 있다는 것을 뜻한다. 예를 들어, c가 6이고 mid가 5라면, nums안에 mid보다 작은 값을 가진 숫자가 6개가 있다는 것인데, 도메인 [low, mid)에서 중복되는 숫자가 없다면, c는 5보다 큰 값을 가질 수 없다. 즉, c값이 6이라는 것은 [low, mid)에 중복되는 값이 있다는 것이다. 그 반대의 경우, 즉 c가 더 큰 경우는 반대로 생각하면 된다. 이렇게 interval을 점차 줄이며 duplicate을 찾아낸다. Runtime과 Space complexities를 분석하자면, low와 high의 중간값(pivot = mid)을 이용하여 while loop은 O(logn)만큼 돌아간다. 그 안에 for loop이 있는데, 이는 nums의 길이만큼 반복하므로 O(n)이다. 따라서 rumtime complexity는 O(logn * n) = O(nlogn)이 된다. 또한 추가로 사용한 space 역시 constant이므로 O(1)이다. 이 솔루션의 경우 follow ups의 조건을 모두 만족시킨다. 

 

사실 Cycle detection을 이용한다면 runtime O(n) space (1)의 솔루션이 나온다. 하지만 내용이 너무 길어질 것 같으므로 생략...!!!