Chương trình tìm tất cả số thiếu từ 1 đến N trong Python

Cho danh sách nums kích thước n chứa số trong [1, n] (có thể trùng). Tìm tất cả số trong [1, n] không xuất hiện trong danh sách, trả về tăng dần. Yêu cầu thời gian tuyến tính, không gian hằng số.

Ví dụ

Đầu vào: [4, 4, 2, 2, 6, 6].
Đầu ra: [1, 3, 5].

Thuật toán

1. Tạo mảng arr kích thước len(nums)+1 khởi tạo 0.
2. Duyệt nums, tăng arr[i].
3. Duyệt arr, nếu arr[i]==0 và i!=0 thì thêm i vào kết quả.

Mã nguồn Python

class Solution:
    def solve(self, nums):
        arr = [0] * (len(nums) + 1)
        for i in nums:
            arr[i] += 1
        missing = []
        for i in range(len(arr)):
            if arr[i] == 0 and i != 0:
                missing.append(i)
        return missing

ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))

Đầu vào / Đầu ra

Input: [4, 4, 2, 2, 6, 6]
Output: [1, 3, 5]