Chương trình tìm số nguyên dương nhỏ nhất bị thiếu trong mảng trong Python

Cho danh sách (có thể có trùng lặp, số âm). Tìm số nguyên dương nhỏ nhất không có trong mảng (First Missing Positive).

Ví dụ: → kết quả 2.

Giải thuật (Hash Set O(n))

1. Tạo set chỉ chứa số > 0.
2. Nếu set rỗng: trả về 1.
3. Duyệt từ 1 đến : nếu không trong set → trả về .

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        nums = set(num for num in nums if num > 0)
        if not nums:
            return 1
        for i in range(1, len(nums) + 2):
            if i not in nums:
                return i

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

Đầu vào

[0, 3, 1]

Đầu ra

2