用 Python 查找重复数字

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

要解决这个问题，我们将按照以下步骤操作：

  • a := nums[0] 且 b := nums[0]
  • while True
    • a := nums[nums[a]]
    • b := nums[b]
    • if a = b, 则退出循环
  • ptr := nums[0]
  • while 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

更新日期： 04-May-2020

2K+ 次浏览

开启你的职业生涯

完成课程，获得认证

开始学习
广告