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:

How can we prove that at least one duplicate number must exist in nums?

Can you solve the problem without modifying the array nums?

Can you solve the problem using only constant, O(1) extra space?

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)

重複が見つかった場合は、すぐに戻ります.

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