[leetcode-python3] 287. Find the Duplicate Number

2748 ワード

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