โปรแกรมหาตัวเลขบวกที่หายไปลำดับที่ k ในอาร์เรย์ Python

ภาพรวม

ให้อาร์เรย์ nums ที่เรียงจากน้อยไปมาก และไม่มีค่าซ้ำ พร้อมจำนวนเต็ม k ต้องการหาตัวเลขบวกที่หายไปจากอาร์เรย์ลำดับที่ k

ตัวอย่าง

nums = [1,2,4,8,12], k = 6

ตัวเลขที่หายไป: [3,5,6,7,9,10,11,...] → ตัวที่ 6 คือ 10

ขั้นตอนการแก้ปัญหา (Brute Force)

1. แปลง nums เป็น Set เพื่อค้นหา O(1)
2. ตั้งค่า count = 0, num = 1
3. วนลูป while count < k:
   • ถ้า num ไม่อยู่ใน Set ให้ count += 1
   • ถ้า count == k ให้คืนค่า num
   • num += 1

ตัวอย่างโค้ด (Python)

def solve(nums, k):
    nums = set(nums)
    count = 0
    num = 1
    while count < k:
        if num not in nums:
            count += 1
        if count == k:
            return num
        num += 1
    return num

nums = [1,2,4,8,12]
k = 6
print(solve(nums, k))

อินพุต

[1,2,4,8,12], 6

เอาต์พุต

10

หมายเหตุ

วิธีนี้ใช้เวลา O(k) ซึ่งอาจช้าถ้า k ใหญ่มาก สามารถปรับปรุงด้วย Binary Search ได้เป็น O(log n)