[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:
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
Reference
この問題について([leetcode-python3] 287. Find the Duplicate Number), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh5408/leetcode-python3-287.-Find-the-Duplicate-Numberテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol