Chương trình tìm số nguyên dương thiếu đầu tiên trong khoảng trong Python

Cho danh sách số nguyên khác nhau đã sắp xếp kích thước . Tìm số nguyên dương đầu tiên trong khoảng [1, n+1] không có trong mảng.

Ví dụ: → kết quả 2 (khoảng 1..5, thiếu 2).

Giải thuật (Duyệt một lần O(n))

1. Khởi tạo .
2. Duyệt từng trong mảng:
   • Nếu : .
3. Trả về .

Ví dụ minh họa

class Solution:
    def solve(self, arr):
        target = 1
        for i in arr:
            if i == target:
                target += 1
        return target

ob = Solution()
nums = [0, 5, 1]
print(ob.solve(nums))  # Output: 2

Đầu vào

[0, 5, 1]

Đầu ra

2