在Python中查找重复编号

假设我们有一个包含n + 1整数的数组nums。成员的范围是1到n。证明至少必须有一个重复的号码。假设只有一个重复的数字，我们必须找到该重复的元素。因此，如果数组类似于[1,3,4,2,2]，则重复元素将为2。

为了解决这个问题，我们将遵循以下步骤-

• a：= nums [0]和b：= nums [0]

• 而真

• 一个：= nums [nums [a]]

• b：= nums [b]

• 如果a = b，则破坏

• ptr：= nums [0]

• 而ptr不是b

• ptr：= nums [ptr]

• b：= nums [b]

• 返回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