중복 찾기 - Leetcode#287-Python

개발자 여러분, 안녕하세요!
당신이 전염병 발생 상황 전체에서 양호한 모습을 보이고 건강을 유지하기를 바랍니다.
나는 오늘 내가 배운 문제에 관한 매우 재미있고 어려운 해결 방안에 관한 글을 쓰고 싶다.

Finding the duplicate number within an array/list.

어떤 일을 하기 전에 먼저 보십시오Leetcode problem statement.
그것을 해결하려고 시도하다.니가 못해도 괜찮아.이것은 매우 이상한 문제다.
주어진

NUM 목록에는 n+1개의 정수가 있습니다.

,nums의 각num의 범위는 1이다.n(포함).

목록에는 중복 번호가 하나만 있습니다.

다양한 솔루션

목록을 훑어보고 정렬한 다음 인접한 두 NUM이 동일한지 확인하고 그 중 한 NUM으로 돌아갑니다.

보이는 num을 다른 목록에 저장합니다. 만약num이 seen에 있다면num을 되돌려줍니다.

그 밖에 문제의 후속 설명을 주의하시기 바랍니다

공간 복잡도는 O(1) - 상수 공간이어야 한다.

시간 복잡도는 O(n^2)보다 작아야 한다.

흠, 네.후속 지침에 맞는 솔루션 정보
이진 검색이 하나의 해결 방안으로 열거되어 있는 것을 보았습니다. 공간의 복잡도가 변하지 않는 상황에서 시간의 복잡도를 절반으로 낮출 수 있습니다. (so O (log n)그러나 나는 다른 해결 방안에 대해 더욱 흥미를 느낀다. 이것은 좀 도전적이다.왠지 모르게 나는 대략 하루가 걸려서야 비로소 이 점을 알게 되었다.

nums = [2,6,4,1,3,1,5]
Output - 1

이 생각은 두 가지 지침-slow과fast가 있다.현재 숫자를 다음 교체할 요소의 인덱스로 사용하면 목록에서 이동합니다.예전과 같이 fast 두 걸음 앞서다.반복 요소로 인해 발생하는 순환을 포함하는 체인 테이블을 생성합니다.
따라서 이 문제는 problem 체인 테이블에서 순환을 찾는 것으로 바뀌었다.
새로운 문제 진술
순환하는 입구 노드/요소를 찾을 체인 테이블을 지정합니다.
왜 우리는 순환의 출발점을 찾아야 합니까?
계속 읽어 주세요.
체인 테이블 구축
현재, 우리는 반복 slow (위와 같이) 을 통해 체인 테이블을 만들어서 디지털 서열을 찾을 것이다.복사본은 같은 값을 가지고 원본 값으로 연결되어 순환을 생성합니다.번호 옆에 있는 () 에는 다음 번호를 식별하는 방법에 대한 설명이 나와 있습니다.nums첫 번째 원소부터 시작합니다.[2,6,4,1,3,1,5]이 서열은 아직 계속되고 있다.이것은 순환이다.우리가 이 점을 보았을 때, 우리는 빌어먹을, 지금 이 순환은 어디에서 시작되는가!?
자, 우선 여기서 체인 시계의 시각적 보조를 구성하겠습니다.
Leetcode 덕분에 우리는 그것을 가지게 되었다.

지금 방법이에요.
반복 요소는 숫자 목록에 존재하는 순환의 입구입니다.잠깐만, 뭐야?
두 단계

2 -> 4(nums[2]) -> 3(nums[4]) -> 1(nums[3]) -> 6(nums[1]) -> 5(nums[6]) -> 1(nums[5]) -> 6(nums[1]) -> 5(nums[6]) -> 1(nums[5]) -> .... - 목록을 훑어볼 때 어느 점에서 Find if there's a loop와 slow 포인터가 같은 노드를 가리키면 그렇습니다. 순환이 있습니다.fast 두 노드를 앞으로 이동하고 있기 때문에 fast 및 fast 은 순환이 있을 때만 같은 노드를 가리킨다.

slow

우리 어떻게 해야 돼요?
그리고 Find the starting node of the cycle.과fast가 가리키는 노드를 찾았으니 되돌아갈 수 없나요?
응, 없어.
왜?
교차 노드가 반드시 중복된 원소/노드는 아니다. 왜냐하면 이 교차 노드는 slow 따라잡기fast 또는 slow 바늘과 무작위로 만나는 순환 중의 노드이기 때문이다. - 이것은 체인 테이블에 하나의 순환이 존재한다는 것을 증명할 뿐이다.
정확한 중복 원소를 얻기 위해서는 이 순환/순환의 기원을 살펴야 한다.
이 원점을 찾기 위해서는 fast 바늘을 목록의 시작 부분으로 밀어 넣고 같은 속도로 slow 바늘과 slow 바늘을 이동해야 한다. 매번 바늘이 같은 노드에서 만났을 때, 즉 순환/순환의 시작이다.
수학적인 것들
만약 우리가 1단계에서 fast과slow를 확정했다고 가정하자.D = the number of steps/distance from the start of the linked list to the start of the cycle가 시작점(0)으로 이동하기 때문에 K = the number of steps/distance from the start of the cycle to the intersection point 걸음 뒤의 위치는 slow이다.D 포인터가 교차점에서 계속되므로 D 걸음 뒤에 있는 위치는 nC(일부 순환수)-K로 D=>fast이제 우리는 그것을 제거했다. 그것을 엮을 때가 되었다.

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

이 솔루션을 이해하는 데 어려움을 겪고 있는 경우 필요한 리소스

고라프 센(Gaurav Sen)이 체인 시계에서 주기가 시작되는 놀라운 행동을 찾았다.적어도 두 번은 보면 너는 알게 될 것이다.

Floyd's cycle detection algorithm 위키백과에서.

This 멋진 솔루션입니다.

쿨한 유튜브라도 이 문제를 해결하기 위해 노력하고 있다는 것을 알아야 한다.

또한 검색 체인 테이블에 순환과 검색 순환의 입구/시작 노드 간의 차이가 있는지 알아보는 것이 중요하다.

그 밖에 this Stack Overflow 답안은 학습 과정에서 많은 문제 답안의 출처이다.

물론 Leetcode 솔루션의 설명을 보십시오.

읽어주셔서 감사합니다.이 문제의 해결 방안은 이해하기 어렵다. 소, 만약 네가 학습 과정에 갇히면 (나도!)꼭 말해줘, 내가 도움이 될지도 몰라.