पायथन में लापता संख्या

मान लीजिए हमारे पास 0 से n तक की संख्याओं की एक सूची है। एक संख्या गायब है। हमें एक कुशल दृष्टिकोण में लापता संख्या ढूंढनी है। उदाहरण के लिए, यदि A = [0, 1, 2, 3, 4, 5, 7, 8, 9], तो लापता संख्या 6 है।

इसे हल करने के लिए हम बाइनरी सर्च दृष्टिकोण का उपयोग करेंगे।

• सूची को आरोही क्रम में क्रमबद्ध करें
• high = A की लंबाई, और low = 0
• जब तक low < high, करें
  • mid = low + (high - low)/2
  • यदि A[mid] > mid
    • high = mid
  • अन्यथा
    • low = mid + 1
• low वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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