ไม่มีตัวเลขใน Python

สมมติว่าเรามีรายการตัวเลขตั้งแต่ 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