Tìm 4 số bị thiếu trong mảng chứa các phần tử từ 1 đến N trong C++

Khái niệm

Cho mảng các số nguyên duy nhất, mỗi số nằm trong khoảng [1, N], kích thước mảng là (N-4) và không có phần tử trùng lặp. Do đó, 4 số từ 1 đến N bị thiếu trong mảng. Tìm 4 số thiếu đó theo thứ tự tăng dần.

Đầu vào

arr[] = {3, 6, 7, 4, 10}

Đầu ra

1 2 5 8 9

Đầu vào

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

Đầu ra

1 3 7 12

Phương pháp

Giải pháp O(N) đơn giản: dùng mảng phụ kích thước N đánh dấu phần tử đã gặp. Duyệt mảng đầu vào, đánh dấu trong mảng phụ. Cuối cùng in các chỉ số chưa được đánh dấu.

Làm thế nào để giải với không gian phụ O(1)?

Khởi tạo mảng helper độ dài 4 để bù 4 số thiếu, điền 0. Duyệt i từ 0 đến độ dài mảng đầu vào, lấy giá trị tuyệt đối của phần tử i gán vào temp. Kiểm tra:

• Nếu giá trị tuyệt đối <= độ dài mảng đầu vào: nhân arr[temp] với -1 (đánh dấu đã gặp).
• Nếu giá trị tuyệt đối > độ dài mảng: gán helper[temp % độ dài mảng] = -1 (đánh dấu).

Duyệt mảng đầu vào: các chỉ số vẫn > 0 là phần tử không gặp, in (index+1).

Duyệt helper: các chỉ số vẫn >= 0 là phần tử không gặp, in (index + độ dài mảng + 1).

Ví dụ

// CPP tìm 4 phần tử thiếu trong mảng kích thước N, phần tử từ 1 đến N+4
#include <bits/stdc++.h>
using namespace std;

// Tìm 4 số thiếu O(N) thời gian, O(1) không gian phụ
void missing4(int arr1[], int n1){
    int helper[4];
    for (int i = 0; i < n1; i++) {
        int temp1 = abs(arr1[i]);
        if (temp1 <= n1)
            arr1[temp1 - 1] *= (-1);
        else if (temp1 > n1) {
            if (temp1 % n1 != 0)
                helper[temp1 % n1 - 1] = -1;
            else
                helper[(temp1 % n1) + n1 - 1] = -1;
        }
    }
    for (int i = 0; i < n1; i++)
        if (arr1[i] > 0)
            cout << (i + 1) << " ";
    for (int i = 0; i < 4; i++)
        if (helper[i] >= 0)
            cout << (n1 + i + 1) << " ";
    return;
}

int main(){
    int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    missing4(arr1, n1);
    return 0;
}

Đầu ra

1 3 7 12