Leetcode Daily Challenge - 중복 번호 찾기

오늘의 Leetcode 챌린지는 인터뷰에서 자주 묻는 문제를 기반으로 합니다. 중간 수준의 문제이며 정렬 방식과 투 포인터 방식을 사용하여 문제에 대한 몇 가지 솔루션을 생각해 냈습니다.

Find the Duplicate Number

직관

직감은 실제 구현과 비교할 때 매우 간단합니다. 그러나 시간 공간 트레이드 오프는 이 문제의 실제 위기입니다. 가장 좋은 방법이 항상 가장 중요한 요구 사항이기 때문에 다양한 방법으로 해결할 수 있습니다.

논리: (접근 a)

이 접근 방식은 명백한 정렬 이유 때문에 목록을 가져와 O(nlogn)에서 요소를 찾을 수 있는지 확인하기 위해 정렬하므로 가장 쉽습니다.

연산:

1. Sort the input list
2. Traverse through list
     if nums[i] == nums[i+1]
       return nums[i]
3. Return -1    

로직(접근 b)

이 접근 방식은 두 부분으로 분기될 수 있는 Floyd Circle 알고리즘을 사용하여 적용할 수 있습니다. 먼저 목록에 주기가 있는지 확인합니다.

또한 반복되는 요소에 대한 인덱싱을 사용하여 확인합니다.

코드 번호 1

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

코드 번호 2

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        turtle = 0
        hare = 0
        while True:
            if turtle >= len(nums):
                turtle = 0
            if hare >= len(nums):
                hare = 0
            if nums[turtle] == nums[hare] and turtle != hare:
                return nums[turtle]
            turtle += 1
            hare += 1
        return None