파이썬에서 중복 번호 찾기

n + 1개의 정수를 포함하는 배열 num이 있다고 가정합니다. 멤버의 범위는 1에서 n까지입니다. 최소한 하나의 중복 번호가 있어야 함을 증명하십시오. 중복 번호가 하나만 있다고 가정하면 해당 중복 요소를 찾아야 합니다. 따라서 배열이 [1,3,4,2,2]와 같으면 중복 요소는 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• a :=nums[0] 및 b :=nums[0]
• 참인 동안
  • a :=nums[nums[a]]
  • b :=숫자[b]
  • =b이면 중단
• ptr :=숫자[0]
• ptr이 b가 아닌 동안
  • ptr :=숫자[ptr]
  • b :=숫자[b]
• 리턴 포인트

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution(object):
   def findDuplicate(self, nums):
      hare = nums[0]
      tortoise = nums[0]
      while True:
         hare = nums[nums[hare]]
         tortoise = nums[tortoise]
         if hare == tortoise:
            break
      ptr = nums[0]
      while ptr!=tortoise:
         ptr = nums[ptr]
         tortoise = nums[tortoise]
      return ptr
ob1 = Solution()
print(ob1.findDuplicate([3,1,3,4,2]))

입력

[3,1,3,4,2]

출력

3