287. Find the Duplicate Number - python3

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(n2)?

My Answer 1: Accepted (Runtime: 2072 ms - 5.13% / Memory Usage: 18.5 MB - 9.24%)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        numset = set(nums)
        
        for i in numset:
            nums.remove(i)
        
        return nums[0]

오늘도 전 런타임 5% 를 보았읍니다...

nums 를 안건들이고 해보래서 했더니만..

set 으로 중복을 없애고 nums 에서 numset 에 있는 애들을 제거해주면 중복만 남기 때문에 남은 nums[0] 을 반환

근데 생각해보니까 굳이 nums 를 모두 볼 필요가 없음

My Answer 2: Accepted (Runtime: 64 ms - 69.69% / Memory Usage: 18.4 MB - 6.85%)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        numset = set()
        
        for i in nums:
            if i in numset:
                return i
            numset.add(i)

그냥 중복 발견하면 바로 return

My Answer 3: Accepted (Runtime: 1712 ms - 6.05% / Memory Usage: 16.5 MB - 54.42%)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        stack = []
        
        for i in nums:
            if i in stack:
                return i
            stack.append(i)

stack 이용해서 중복을 발견하면 break 하고 반환

set 이랑 방식은 같은데 훨씬 느림

My Answer 4: Accepted (Runtime: 68 ms - 43.71% / Memory Usage: 16.6 MB - 54.42%)

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

이번엔 sort 로 정렬 후 중복 찾아주기

Solution

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        
        # Find the "entrance" to the cycle.
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        
        return hare