파이썬에서 누락된 숫자

0에서 n까지의 숫자 목록이 있다고 가정합니다. 누락된 숫자가 하나 있습니다. 효율적인 접근 방식으로 누락된 숫자를 찾아야 합니다. 따라서 A =[0, 1, 2, 3, 4, 5, 7, 8, 9]인 경우 누락된 숫자는 6입니다.

이 문제를 해결하기 위해 바이너리 검색 방식을 사용할 것입니다.

• 오름차순으로 목록 정렬
• 높은 =A의 길이, 낮은 =0
• 낮은 동안 <높은, do
  • 중간 =낮음 + (높음 – 낮음)/2
  • A[mid]인 경우> mid
    • 높음 =중간
  • 그렇지 않으면
    • 낮음 =중간 + 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