Chương trình C++ tách mảng và thêm phần đầu vào cuối

Tách mảng tại vị trí k, đưa phần đầu (0 đến k-1) lên cuối mảng.

Ví dụ

Mảng gốc: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
K = 4 (tách sau index 3)
Kết quả: {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}

Thuật toán

Lặp k lần: lấy phần tử đầu, dịch toàn mảng trái 1 vị trí, đặt phần tử đó lên cuối.

Độ phức tạp: O(n × k). Có thể tối ưu thành O(n) bằng reversal algorithm.

Code cơ bản (O(n×k))

#include <iostream>
using namespace std;

void splitArray(int arr[], int n, int k) {
    for(int i = 0; i < k; i++) {
        int x = arr[0];           // Lấy phần tử đầu
        for(int j = 0; j <= n-2; j++)
            arr[j] = arr[j+1];    // Dịch trái
        arr[n-1] = x;             // Đặt lên cuối
    }
}

int main() {
    int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(data)/sizeof(data[0]);
    int k;
    
    cout << "Nhap kich thuoc tach (k): ";
    cin >> k;
    
    splitArray(data, n, k);
    
    for(int i = 0; i < n; i++)
        cout << data[i] << " ";
    return 0;
}

Kết quả

Nhap kich thuoc tach (k): 4
4 5 6 7 8 9 0 1 2 3

Tối ưu O(n) - Reversal Algorithm

void reverse(int arr[], int start, int end) {
    while (start < end)
        swap(arr[start++], arr[end--]);
}

void rotateLeft(int arr[], int n, int k) {
    k = k % n;           // Xử lý k > n
    reverse(arr, 0, k-1);      // Đảo phần đầu
    reverse(arr, k, n-1);      // Đảo phần sau
    reverse(arr, 0, n-1);      // Đảo toàn bộ
}

Cách này chỉ O(n) và là kỹ thuật chuẩn cho array rotation.