Pythonで重複番号を見つける

n+1個の整数を含む配列numがあるとします。メンバーは1からnの範囲です。少なくとも1つの重複番号が存在する必要があることを証明します。重複する番号が1つしかない場合、その重複する要素を見つける必要があります。したがって、配列が[1,3,4,2,2]のような場合、重複する要素は2になります。

これを解決するには、次の手順に従います-

• a：=nums [0]およびb：=nums [0]
• True
  • a：=nums [nums [a]]
  • b：=nums [b]
  • a =bの場合、中断します
• ptr：=nums [0]
• ptrはb
  ではありません
  • ptr：=nums [ptr]
  • b：=nums [b]
• return ptr

理解を深めるために、次の実装を見てみましょう-

例

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