หา 4 ตัวเลขที่หายไปในอาร์เรย์ 1 ถึง N (Python)

โจทย์: อาร์เรย์ขนาด N-4 มีตัวเลข distinct จาก 1 ถึง N หา 4 ตัวที่หายไป (เรียงลำดับ)

ตัวอย่าง: A=[2,8,4,13,6,11,9,5,10] (N=13) → หาย: 1,3,7,12

อัลกอริทึม In-place Marking O(1) Space

ใช้เครื่องหมายลบบนอาร์เรย์เดิม (index = value-1) สำหรับค่า ≤ n ส่วนค่า > n ใช้ array เล็ก temp_arr ขนาด 4

1. วน i: temp = |A[i]|
2. ถ้า temp ≤ n: A[temp-1] *= -1 (mark)
3. ถ้า temp > n: temp_arr[temp % n - 1] = -1 (หรือ index พิเศษสำหรับ mod 0)
4. สแกน A: ค่าบวก → index+1 หายไป
5. สแกน temp_arr: ค่า ≥ 0 → n + index + 1 หายไป

ตัวอย่างโค้ด

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

A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)  # 1 3 7 12

ผลลัพธ์

1 3 7 12

สรุป: เทคนิค in-place marking ใช้เครื่องหมายลบ บวก temp_arr ขนาดคงที่ 4 สำหรับค่า > n O(n) time O(1) extra space