Tìm số trùng lặp trong Python

Giả sử chúng ta có một số mảng chứa n + 1 số nguyên. Các thành viên nằm trong phạm vi từ 1 đến n. chứng minh rằng phải có ít nhất một số trùng lặp. Giả sử rằng chỉ có một số trùng lặp, chúng ta phải tìm phần tử trùng lặp đó. Vì vậy, nếu mảng giống như [1,3,4,2,2], thì phần tử trùng lặp sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• a:=nums [0] và b:=nums [0]
• while True
  • a:=nums [nums [a]]
  • b:=nums [b]
  • nếu a =b, thì ngắt
• ptr:=nums [0]
• trong khi ptr không phải là b
  • ptr:=nums [ptr]
  • b:=nums [b]
• trả lại ptr

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]))

Đầu vào

[3,1,3,4,2]

Đầu ra

3