在 Python 中查找重复数字

pythonserver side programmingprogramming更新于 2025/11/23 0:44:17

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

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

a := nums[0] and b := nums[0]
while True
- a := nums[nums[a]]
- b := nums[b]
- 如果 a = b，则 break
ptr := nums[0]
while ptr is not 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]))