Số dương nhỏ nhất bị thiếu trong Python

Cho mảng số nguyên không sắp xếp, tìm số dương nhỏ nhất bị thiếu. Ví dụ: [4, -3, 1, -1] -> 2.

Các bước giải quyết (Cyclic Sort O(n) time, O(1) space):

• Thêm 0 vào đầu mảng (nums = [0] + nums)
• Duyệt i: بينما nums[i] trong [0, n) và nums[nums[i]] != nums[i], hoán đổi nums[i] và nums[nums[i]]
• Duyệt từ 1: tìm số đầu tiên không xuất hiện tại đúng vị trí

Ví dụ

class Solution(object):
    def firstMissingPositive(self, nums):
        i = 0
        nums = [0] + nums
        for i in range(len(nums)):
            while nums[i] >= 0 and nums[i] < len(nums) and nums[nums[i]] != nums[i]:
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        num = 1
        for i in range(1, len(nums)):
            if num == nums[i]:
                num += 1
        return num

ob = Solution()
print(ob.firstMissingPositive([4, -3, 1, -1]))

Đầu vào

[4, -3, 1, -1]

Đầu ra

2