287. Find the Duplicate Number

문제 링크 : https://leetcode.com/problems/find-the-duplicate-number/

중복된 숫자를 찾는 문제이다.

가장 간단하게 풀 수 있는 방법은 먼저 nums를 정렬해준 뒤, 옆의 숫자와 비교하며 중복된 숫자를 찾는 방법이 있다.

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

Runtime: 1150 ms, faster than 16.65% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 27.9 MB, less than 90.75% of Python3 online submissions for Find the Duplicate Number.

22.08.10 복습

정말 이전 방법과 똑같은 방법으로 풀음

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

근데 원래는 해당 인덱스에 있는 값을 반환하고 싶으면.. len(nums)-1이 맞을텐데 어떻게 성공했지..

네.. 근데..

You must solve the problem without modifying the array nums and uses only constant extra space.

https://www.youtube.com/watch?v=pKO9UjSeLew

쿳소..

다시 복습하면서
플루이드 알고리즘..? 에 대해 알아보고 이를 이용하여 풀어보았다.

일명 토끼와 거북이 알고리즘..?이라고도 하는데
어떤 linked list 에서 토끼가 거북이의 두 배를 이동할 수 있다고 가정하면
결국은 어떤 지점에서 토끼와 거북이가 만나게 된다.. 하는 원리이다.

그리고 이번 해당 문제에서 플로이드 알고리즘을 이용할 수 있는 이유는

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

: 자연수 N과 N + 1 길이를 가진 배열 nums가 주어집니다.
nums에는 1보다 크거나 같고, N보다 작거나 같은 정수만 들어올 수 있습니다.

라는 조건이 주어졌기 때문이다.
그래서 cycled된 리스트..?처럼 풀 수 있다..

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        fast, slow = 0, 0
        while True : 
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast :
                break
        slow2 = 0
        while True: 
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

Runtime: 786 ms, faster than 76.76% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 27.7 MB, less than 98.23% of Python3 online submissions for Find the Duplicate Number.