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

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

সমাধানের ধাপগুলো (ফ্লয়েডের টার্টােজ-হেয়ার অ্যালগরিদম):

• hare := nums[0] এবং tortoise := nums[0]
• সত্য থাকাকালীন
  • hare := nums[nums[hare]]
  • tortoise := nums[tortoise]
  • যদি hare == tortoise, তবে ব্রেক করুন
• ptr := nums[0]
• ptr != tortoise যতক্ষণ
  • ptr := nums[ptr]
  • tortoise := nums[tortoise]
• 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