Nhân đôi phần tử đầu tiên và đẩy số 0 về cuối mảng trong C++

Giới thiệu

Chương trình này xử lý mảng theo quy tắc: nếu hai phần tử liền kề bằng nhau và khác 0, thì nhân đôi phần tử đầu tiên và gán phần tử thứ hai thành 0. Sau đó đẩy tất cả số 0 về cuối mảng.

Ví dụ minh họa

Mảng gốc: {2, 3, 3, 4, 0, 5, 5}

Bước 1 - Xử lý cặp liền kề: {2, 6, 0, 4, 0, 10, 0}

Bước 2 - Đẩy 0 về cuối: {2, 6, 4, 10, 0, 0, 0}

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

void moveZeroesToEnd(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            arr[count++] = arr[i];
        }
    }
    while (count < n) {
        arr[count++] = 0;
    }
}

void updateAndRearrangeArray(int arr[], int n) {
    if (n == 1) return;
    
    for (int i = 0; i < n - 1; i++) {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {
            arr[i] = 2 * arr[i];
            arr[i + 1] = 0;
            i++; // Bỏ qua phần tử đã xử lý
        }
    }
    moveZeroesToEnd(arr, n);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main() {
    int arr[] = {2, 3, 3, 4, 0, 5, 5}, n = 7;
    
    cout << "Mảng gốc: ";
    printArray(arr, n);
    cout << endl;
    
    updateAndRearrangeArray(arr, n);
    
    cout << "Mảng sau xử lý: ";
    printArray(arr, n);
    cout << endl;
    
    return 0;
}

Kết quả chạy chương trình

Mảng gốc: 2 3 3 4 0 5 5
Mảng sau xử lý: 2 6 4 10 0 0 0

Giải thích chi tiết

Hàm moveZeroesToEnd

Sử dụng kỹ thuật two-pointer: con trỏ count theo dõi vị trí đặt phần tử khác 0 tiếp theo. Duyệt mảng, mỗi khi gặp phần tử khác 0, đưa về vị trí count và tăng count. Cuối cùng lấp đầy các vị trí còn lại bằng 0.

Hàm updateAndRearrangeArray

Duyệt mảng từ trái sang phải. Khi tìm thấy cặp phần tử liền kề bằng nhau và khác 0: nhân đôi phần tử đầu, gán phần tử sau = 0, và nhảy qua phần tử đã xử lý (i++).

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

• Thời gian: O(n) - duyệt mảng 2 lần
• Không gian: O(1) - xử lý tại chỗ (in-place)

Kết luận

Bài toán kết hợp xử lý mảng và kỹ thuật two-pointer, thường gặp trong các bài tập thuật toán và phỏng vấn lập trình.