पायथन में डुप्लिकेट नंबर ढूंढें

मान लीजिए हमारे पास एक ऐरे nums है जिसमें n + 1 पूर्णांक हैं। सदस्य 1 से n की रेंज में हैं। साबित करें कि कम से कम एक डुप्लिकेट नंबर अवश्य होगा। मान लें कि केवल एक डुप्लिकेट नंबर है, हमें उस डुप्लिकेट एलिमेंट को ढूंढना है। इसलिए यदि ऐरे [1,3,4,2,2] जैसा है, तो डुप्लिकेट एलिमेंट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• a := nums[0] और b := nums[0]
• जब तक True
  • 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