[리트코드] 287. Find the Duplicate Number

287. 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] 까지의 숫자가 들어 있는 배열에 추가로 하나의 숫자가 들어 갔을 때 추가된 숫자 찾기

제한사항

• 1 <= n <= 105
• 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.

풀이

카운터로 1 이상인 거 찾기

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        return [k for k, v in collections.Counter(nums).items() if v > 1][0]

그런데? 저장 공간을 하나만 써야 된다. 그래서 중간난이도였던 것 ㄷㄷ

인덱스의 값을 인덱스로 보고 nums 자체 배열을 이용하는 방식이 있다. 인덱스의 값을 확인하고 해당 숫자를 인덱스로 하는 값에 표시를 해준다. 이렇게 쭉 표시를 하다가 해당 숫자를 인덱스로 하는 값이 이미 표시되어 있으면 중복되는 값이므로 정답이 된다.

그래프로 바꿔보면 방향 그래프에서 한 노드를 두 개의 간선이 가리키는 상황이라고 볼 수 있다.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        
        for n in nums:
            if nums[abs(n)] < 0 :
                return abs(n)
            nums[abs(n)] *= - 1

근데 이 방법은 배열을 수정해야한다. 배열을 수정하지 않고 문제를 해결하려면 이진 탐색해야 한다.

target = 반복 되는 수이므로 mid가 반복되는 수가 될 때 까지 이진탐색하면 된다.

• mid를 정한다.
• 배열의 값 중에 mid 보다 작은 수를 카운트한다.
• 배열의 값 중에 mid와 같은 수를 카운트한다.
• 만약 같은 수가 1개 이상이라면 반복되는 수이므로 리턴한다.
• 만약 작은 개수가 미드보다 크다면 왼쪽으로 범위를 이동해 탐색한다.
• 작다면 오른쪽으로 범위를 이동해 탐색한다.

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