ค้นหาหมายเลขที่ซ้ำกันใน Python

สมมติว่าเรามีจำนวนอาร์เรย์ที่มีจำนวนเต็ม n + 1 สมาชิกอยู่ในช่วง 1 ถึง n พิสูจน์ว่าต้องมีหมายเลขที่ซ้ำกันอย่างน้อยหนึ่งหมายเลข สมมติว่ามีหมายเลขที่ซ้ำกันเพียงหมายเลขเดียว เราต้องหาองค์ประกอบที่ซ้ำกันนั้น ดังนั้นหากอาร์เรย์เป็นเหมือน [1,3,4,2,2] องค์ประกอบที่ซ้ำกันจะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• a :=nums[0] และ b :=nums[0]
• ในขณะที่จริง
  • a :=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