পাইথনে ডুপ্লিকেট নম্বর খুঁজুন

ধরুন আমাদের একটি অ্যারে সংখ্যা আছে যেখানে n + 1 পূর্ণসংখ্যা রয়েছে। সদস্যরা 1 থেকে n এর মধ্যে রয়েছে। প্রমাণ করুন যে অন্তত একটি সদৃশ নম্বর সেখানে থাকতে হবে। অনুমান করুন যে শুধুমাত্র একটি ডুপ্লিকেট নম্বর আছে, আমাদের সেই ডুপ্লিকেট উপাদানটি খুঁজে বের করতে হবে। সুতরাং যদি অ্যারেটি [1,3,4,2,2] এর মত হয়, তাহলে ডুপ্লিকেট উপাদানটি 2 হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• a :=সংখ্যা[0] এবং b :=সংখ্যা[0]
• যদিও সত্য
  • a :=সংখ্যা[সংখ্যা[a]]
  • b :=সংখ্যা[b]
  • যদি a =b, তাহলে বিরতি
• ptr :=সংখ্যা[0]
• যদিও ptr b
  নয়
  • ptr :=সংখ্যা[ptr]
  • b :=সংখ্যা[b]
• পিটিআর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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