Sắp xếp mảng sao cho arr[i] = arr[arr[i]] với O(1) bộ nhớ phụ trong C++

Cho mảng số nguyên dương arr[] kích thước n, các phần tử có giá trị từ 0 đến n-1. Nhiệm vụ: sắp xếp lại mảng sao cho arr[i] trở thành arr[arr[i]] chỉ dùng O(1) bộ nhớ bổ sung.

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: int arr[] = {0, 3, 2, 1, 5, 4}

Đầu ra: Mảng trước: 0 3 2 1 5 4
Mảng sau: 0 1 2 3 4 5

Giải thích: arr[arr[0]] = arr[0] = 0; arr[arr[1]] = arr[3] = 1; arr[arr[2]] = arr[2] = 2; arr[arr[3]] = arr[1] = 3; arr[arr[4]] = arr[5] = 4; arr[arr[5]] = arr[4] = 5.

Đầu vào: int arr[] = {1, 0}

Đầu ra: Mảng trước: 1 0 → Mảng sau: 0 1

Đầu vào: int arr[] = {1, 0, 2, 3}

Đầu ra: Mảng trước: 1 0 2 3 → Mảng sau: 0 1 2 3

Phương pháp tiếp cận (O(1) không gian)

• Nhập mảng, tính size, in mảng ban đầu, gọi Rearrangement(arr, size).
• Trong hàm Rearrangement:
  • Vòng lặp i từ 0 đến size-1: temp = arr[arr[i]] % size; arr[i] += temp * size; (lưu giá trị mới và cũ cùng một ô).
  • Vòng lặp i từ 0 đến size-1: arr[i] = arr[i] / size; (lấy giá trị mới).
• In kết quả.

Ví dụ mã C++

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

void Rearrangement(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int temp = arr[arr[i]] % size;
        arr[i] += temp * size;
    }
    for (int i = 0; i < size; i++) {
        arr[i] = arr[i] / size;
    }
}

int main() {
    int arr[] = {0, 3, 2, 1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Array before Arrangement: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    Rearrangement(arr, size);
    cout << "\nRearrangement so that arr[i] becomes arr[arr[i]] with O(1) extra space: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    return 0;
}

Đầu ra chương trình

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5