[LeetCode] 287 | Find the Duplicate Number | Python

---

문제 링크: https://leetcode.com/problems/find-the-duplicate-number/

---

문제

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

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

You must solve the problem without modifying the array nums and uses only constant extra space.

---

조건

• 1 <= n <= $10^5$
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

---

내 풀이

주어진 리스트(nums)에서 중복되는 숫자를 찾는다기보다, $[1, ..., n]$ 내에서 해당하는 원소를 찾는다고 생각한다.

binary search를 이용해 탐색 시간을 줄이고, 아래 원리로 답을 찾는다.

 

만약 (count <= mid)가 성립한다면, 비둘기집 원리(Pigeonhole Principle)에 의해 중복되는 원소는 $[left, mid]$에 존재한다.

성립하지 않는다면, 중복되는 원소는 $[mid+1, right]$에 존재하게 된다.

---

코드

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1
        
        while left < right:
            mid = left + (right-left)//2
            
            count = 0
            for num in nums:
                if num <= mid:
                    count += 1
            
            if count <= mid:
                left = mid + 1
            else:
                right = mid
            
        return left