পাইথনে অনুপস্থিত নম্বর

ধরুন আমাদের কাছে 0 থেকে n পর্যন্ত সংখ্যার একটি তালিকা আছে। অনুপস্থিত একটি সংখ্যা আছে. আমাদের একটি দক্ষ পদ্ধতিতে অনুপস্থিত সংখ্যা খুঁজে বের করতে হবে। সুতরাং A =[0, 1, 2, 3, 4, 5, 7, 8, 9] হলে, অনুপস্থিত সংখ্যা হল 6।

এটি সমাধান করতে, আমরা বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব।

• অধিক্রম অনুসারে তালিকা সাজান
• উচ্চ =A এর দৈর্ঘ্য, এবং নিম্ন =0
• যখন কম <উচ্চ, কর
  • মধ্য =নিম্ন + (উচ্চ - নিম্ন)/2
  • যদি A[মধ্য]> মধ্য
    • উচ্চ =মধ্য
  • অন্যথায়
    • নিম্ন =মধ্য + 1
• কম রিটার্ন

উদাহরণ

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

class Solution(object):
   def missingNumber(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      nums.sort()
      high = len(nums)
      low = 0
      while low<high:
         mid = low + (high-low)//2
         if nums[mid]>mid:
            high = mid
         else:
            low = mid+1
      return low
ob1 = Solution()
print(ob1.missingNumber([5,3,1,7,8,0,9,2,4]))

ইনপুট

nums = [5,3,1,7,8,0,9,2,4]

আউটপুট

6