Editorial for ptit059: Thêm phần tử vào mảng

Hiểu bài toán

Bài toán yêu cầu chèn một số nguyên x vào một mảng tăng dần gồm N phần tử sao cho mảng thu được vẫn tăng dần. Mảng ban đầu được đảm bảo đã được sắp xếp tăng dần. Sau khi chèn, mảng sẽ có N+1 phần tử. Vấn đề chính là tìm vị trí thích hợp để chèn x và đảm bảo các phần tử sau vị trí đó được dịch chuyển.

Các cách tiếp cận

Cách Tìm vị trí và chèn bằng dịch chuyển mảng

#include<stdio.h>

int main() {
    int n, a[10005];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int k, pos = -1;
    scanf("%d", &k);
    // Tìm vị trí đầu tiên có phần tử lớn hơn k
    for (int i = 0; i < n; i++) {
        if (k < a[i]) {
            pos = i;
            break;
        }
    }
    // Nếu không tìm thấy (k lớn hơn tất cả), chèn vào cuối
    if(pos != -1) {
        // Dịch chuyển các phần tử từ pos về sau sang phải
        for (int i = n; i > pos; i--) {
            a[i] = a[i - 1];
        }
        a[pos] = k;
    } else {
        a[n] = k;
    }
    // In mảng kết quả
    for (int i = 0; i < n + 1; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này tìm vị trí chèn (pos) bằng cách duyệt mảng từ đầu đến cuối. Nếu tìm thấy phần tử đầu tiên lớn hơn x, ta ghi nhận vị trí đó và dừng lại. Nếu không tìm thấy (x lớn hơn tất cả các phần tử), pos sẽ là cuối mảng (hoặc một flag đặc biệt). Sau đó, ta cần dịch chuyển các phần tử từ vị trí pos trở về sau sang phải 1 đơn vị để giải phóng chỗ cho x. Thao tác dịch chuyển này có độ phức tạp O(n) trong trường hợp xấu nhất (chèn vào đầu mảng). Cuối cùng, gán a[pos] = x và in ra mảng.

Cách Sử dụng mảng động và chèn vào cuối rồi sắp xếp

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int n, x, i, j;
    scanf("%d", &n);
    int a[n+1]; // Mảng đủ chỗ cho N+1 phần tử
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &x);
    a[n]=x; // Đưa x vào cuối mảng
    // Sử dụng Bubble Sort hoặc Insertion Sort một bước để đưa x về đúng vị trí
    // Code mẫu sử dụng logic tương tự Insertion Sort/Bubble Sort
    for (i=0; i<n; i++) {
        if (a[i] > a[n]) {
            int tmp = a[i];
            a[i] = a[n];
            a[n] = tmp;
        }
    }
    for (i=0; i<n+1; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Phương pháp này tận dụng việc mảng ban đầu đã được sắp xếp. Đầu tiên, ta đưa phần tử x vào vị trí cuối cùng của mảng (đã cấp phát đủ kích thước N+1). Sau đó, thực hiện một vòng lặp duyệt từ đầu mảng. Nếu gặp phần tử nào lớn hơn x, ta hoán đổi nó với x. Đây về cơ bản là bước đầu tiên của thuật toán Insertion Sort hoặc Bubble Sort để 'đẩy' x về đúng vị trí. Vì mảng ban đầu đã tăng dần, x sẽ chỉ cần 'đẩy' lui một đoạn duy nhất cho đến khi gặp phần tử lớn hơn nó hoặc hết mảng. Độ phức tạp vẫn là O(n) trong trường hợp xấu nhất.

Cách Sử dụng mảng tĩnh và chỉ số duyệt

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ll long long
#define sc scanf
#define pr printf

int main() {
    int n, x; sc("%d", &n);
    int a[100005]; // Mảng tĩnh lớn
    for(int i=0; i<n; i++) sc("%d", &a[i]);
    sc("%d",&x);

    int vitrichen = n; // Mặc định chèn vào cuối
    for(int i=0; i<n; i++){
        if(x < a[i]){
            vitrichen = i;
            break;
        }
    }
    // Dịch chuyển phần tử
    for(int j=n; j>vitrichen; j--){
        a[j] = a[j-1];
    }
    a[vitrichen] = x;
    // In kết quả
    for(int k=0; k<n+1; k++)
        pr("%d ", a[k]);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là biến thể trực tiếp nhất của phương pháp dịch chuyển mảng. Nó dùng một biến vitrichen để lưu vị trí cần chèn. Vòng lặp đầu tiên tìm vị trí này. Vòng lặp thứ hai (duyệt ngược) thực hiện dịch chuyển các phần tử. Cách này rõ ràng và dễ hiểu, xử lý được các trường hợp đặc biệt (chèn đầu, chèn cuối, chèn giữa) một cách gọn gàng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Mảng ban đầu đã được sắp xếp tăng dần là thông tin quan trọng nhất giúp giảm độ phức tạp.
• Vị trí chèn là chỉ số đầu tiên mà tại đó phần tử của mảng lớn hơn x. Nếu không có, vị trí chèn là N.
• Để chèn vào mảng tĩnh, ta bắt buộc phải dịch chuyển các phần tử hiện có để tạo khoảng trống.

Lỗi thường gặp

• Quên cấp phát mảng có kích thước N+1 dẫn đến tràn bộ nhớ (buffer overflow) khi chèn phần tử mới.
• Lỗi logic khi duyệt để tìm vị trí chèn (ví dụ: sử dụng > thay vì >= có thể thay đổi hành vi nếu có phần tử bằng x, mặc dù đề bài không rõ ràng về số trùng lặp, nhưng thường chèn ngay sau phần tử bằng hoặc trước đều được, cần nhất quán).
• Lỗi dịch chuyển mảng: duyệt từ đầu về cuối sẽ ghi đè dữ liệu chưa xử lý, phải duyệt từ cuối về đầu.