Hiểu bài toán

Bài toán yêu cầu thực hiện một phép chuyển đổi (dịch chuyển) trên một mảng gồm N phần tử. Cụ thể, với hai số nguyên N và K, ta cần đọc một mảng A gồm N phần tử và in ra mảng mới sau khi thực hiện dịch chuyển trái K phần tử. Phép dịch chuyển trái K phần tử có nghĩa là: phần tử ở vị trí i sẽ chuyển đến vị trí (i - K) (tính theo modulo N). Do đó, phần tử tại vị trí K+1 (vị trí thứ K nếu tính từ 0) sẽ trở thành phần tử đầu tiên của mảng kết quả. Ví dụ: mảng [1, 2, 3, 4, 5] với K=2 sẽ trở thành [3, 4, 5, 1, 2].

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

Cách Xử lý trực tiếp theo số dư K % N

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

int main()
{
    freopen("CHUYENDOI.INP", "r", stdin);
    freopen("CHUYENDOI.OUT", "w", stdout);
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    int d = k % n; // Xử lý trường hợp K lớn hơn N

    for (int i = 0; i < n; i++){
        cin >> v[i];
    }

    // In ra các phần tử từ vị trí K đến hết
    for (int i = d; i < n; i++){
        cout << v[i] << " ";
    }
    // In ra các phần tử từ vị trí 0 đến K-1
    for (int i = 0; i < d; i++){
        cout << v[i] << " ";
    }

    return 0;
}

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

Đây là cách tiếp cận trực quan và hiệu quả nhất.

1. Đọc dữ liệu vào N, K và mảng A.
2. Tính K = K % N để đảm bảo K nằm trong khoảng [0, N-1] (vì dịch chuyển N lần trở về vị trí ban đầu).
3. In các phần tử từ chỉ số K đến N-1.
4. In các phần tử từ chỉ số 0 K-1. Cách này xử lý đúng yêu cầu bài toán với chi phí thời gian và bộ nhớ tối ưu.

Cách Sử dụng mảng phụ

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

int main() {
    freopen("chuyendoi.inp", "r", stdin);
    freopen("chuyendoi.out", "w", stdout);
    int N, K;
    cin >> N >> K;

    if (K % N == 0) {
        // Nếu K chia hết cho N, mảng không thay đổi
        for (int n = 0; n < N; n++) {
            int a;
            cin >> a;
            cout << a << " ";
        }
    } else {
        int b = K % N;
        int arr[N];
        // Đọc và sắp xếp vào mảng theo thứ tự mới
        // Các phần tử cuối (bản gốc từ K đến N) vào vị trí đầu
        for (int i = N - b; i < N; i++) {
            int c;
            cin >> c;
            arr[i] = c;
        }
        // Các phần tử đầu (bản gốc từ 0 đến K) vào vị trí sau
        for (int j = 0; j < N - b; j++) {
            int d;
            cin >> d;
            arr[j] = d;
        }
        // In mảng
        for (int m : arr) {
            cout << m << " ";
        }
    }
    return 0;
}

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

Cách này cũng sử dụng logic chia đôi mảng tương tự Approach 1 nhưng thực hiện việc đọc dữ liệu và gán vào một mảng phụ (hoặc mảng mới) sao cho các phần tử được đặt đúng vị trí ngay từ đầu.

1. Tính K = K % N.
2. Đọc N - K phần tử đầu tiên và gán vào các vị trí cuối cùng của mảng mới (từ K trở đi).
3. Đọc K phần tử còn lại và gán vào các vị trí đầu tiên của mảng mới.
4. In ra mảng. Cách này cần một mảng lưu trữ riêng để gán đúng vị trí trước khi in.

Cách Sử dụng cấu trúc dữ liệu Queue (Hàng đợi)

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

int main() {
    freopen("chuyendoi.inp", "r", stdin);
    freopen("chuyendoi.out", "w", stdout);
    int N, K;
    cin >> N >> K;
    queue<int> q;

    // Đọc tất cả vào queue
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        q.push(x);
    }

    // Xoay K phần tử
    K %= N;
    for (int i = 0; i < K; i++) {
        int front = q.front();
        q.pop();
        q.push(front);
    }

    // In ra queue
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

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

Sử dụng cấu trúc dữ liệu Queue để mô phỏng quá trình dịch chuyển.

1. Đọc toàn bộ mảng vào Queue.
2. Thực hiện K thao tác: lấy phần tử đầu ra (pop) và đưa xuống cuối hàng đợi (push).
3. In ra các phần tử trong Queue. Cách này dễ hiểu về mặt logic (mô phỏng hành động), nhưng thường tốn kém hơn về mặt thời gian thực thi (constant time overhead) và bộ nhớ so với hai cách trên.

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

Bài học kinh nghiệm

• Phép dịch chuyển trái K phần tử tương đương với việc chia mảng thành 2 đoạn: đoạn thứ nhất từ K đến N-1, đoạn thứ hai từ 0 đến K-1.
• Khi K >= N, vị trí không đổi sau K lần dịch, do đó chỉ cần quan tâm đến K % N.
• Nếu K % N == 0, mảng đầu ra giống hệt mảng đầu vào.

Lỗi thường gặp

• Quên xử lý trường hợp K > N (dẫn đến chỉ số truy cập ngoài mảng hoặc logic sai nếu dùng mảng tĩnh).
• Sử dụng biến toàn cục chưa khởi tạo.
• Lỗi thứ tự nhập/xuất: nhập xong mới tính toán hoặc in sai thứ tự 2 đoạn.