पायथन में डुप्लिकेट नंबर खोजें

मान लीजिए कि हमारे पास 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:=nums[ptr]
  • b :=nums[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