สมมติว่าเรามีรายการตัวเลขจาก 0 ถึง n มีตัวเลขหนึ่งตัวที่หายไป เราต้องหาตัวเลขที่หายไปด้วยวิธีที่มีประสิทธิภาพ เช่นถ้า A = [0, 1, 2, 3, 4, 5, 7, 8, 9] ตัวเลขที่หายไปคือ 6
ในการแก้ปัญหานี้ เราจะใช้วิธีการค้นหาแบบทวิภาค (binary search)
- เรียงลำดับรายการในลำดับน้อยไปมาก
- high = ความยาวของ A, และ low = 0
- while 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
