โปรแกรมหาตัวเลขที่หายไปลำดับที่ K จากรายการที่เรียงแล้วใน Python

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

ตัวอย่างเช่น nums = [5, 6, 8, 10, 11], k = 1 ผลลัพธ์คือ 9 (ตัวเลขหายไปตัวที่ 2 คือ 9)

ขั้นตอนการแก้ปัญหา (Linear Scan)

1. วนลูป i จาก 1 ถึง len(nums) - 1:
   • diff = nums[i] - nums[i-1] - 1 (จำนวนตัวเลขหายไประหว่างคู่นี้)
   • หาก k >= diff ให้ k -= diff
   • มิฉะนั้น คืนค่า nums[i-1] + k + 1
2. หากวนจบไม่เจอ คืนค่า nums[-1] + k + 1

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

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            diff = nums[i] - nums[i - 1] - 1
            if k >= diff:
                k -= diff
            else:
                return nums[i - 1] + k + 1
        
        return nums[-1] + k + 1

ob = Solution()
nums = [5, 6, 8, 10, 11]
k = 1
print(ob.solve(nums, k))  # Output: 9

อินพุต

[5, 6, 8, 10, 11], 1

เอาต์พุต

9