Tìm 4 số thiếu trong mảng chứa các số từ 1 đến N trong Python

Cho mảng các số khác nhau trong khoảng [1, N], kích thước mảng là N-4 (thiếu 4 số). Tìm 4 số thiếu theo thứ tự tăng dần.

Ví dụ: A = [2, 8, 4, 13, 6, 11, 9, 5, 10] → Kết quả: [1, 3, 7, 12].

Thuật toán dùng mảng phụ và dấu âm

1. Tạo temp_arr size 4 toàn 0 (dành cho 4 số > N-4).
2. Duyệt A: lấy temp = |A[i]|.
   • Nếu temp ≤ len(A): đổi dấu A[temp-1] *= -1.
   • Nếu temp > len(A): đánh dấu trong temp_arr tại vị trí temp % len(A) - 1 (xử lý riêng khi chia hết).
3. Duyệt A: chỉ số i có A[i] > 0 → số thiếu i+1.
4. Duyệt temp_arr: phần tử ≥ 0 → số thiếu len(A) + i + 1.

Ví dụ code

def find_missing_nums(A):
    temp_arr = [0] * 4
    for i in range(len(A)):
        temp = abs(A[i])
        if temp <= len(A):
            A[temp - 1] *= -1
        elif temp > len(A):
            if temp % len(A):
                temp_arr[temp % len(A) - 1] = -1
            else:
                temp_arr[(temp % len(A)) + len(A) - 1] = -1
    for i in range(len(A)):
        if A[i] > 0:
            print(i + 1, end=" ")
    for i in range(len(temp_arr)):
        if temp_arr[i] >= 0:
            print(len(A) + i + 1, end=" ")

A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)

Input

[2, 8, 4, 13, 6, 11, 9, 5, 10]

Output

1 3 7 12