Sắp xếp mảng sao cho arr[j] thành i nếu arr[i] là j trong C++

Cho một mảng số nguyên dương arr[] kích thước bất kỳ, các phần tử có giá trị lớn hơn 0 nhưng nhỏ hơn kích thước mảng. Nhiệm vụ là sắp xếp lại mảng sao cho nếu arr[j] = j thì arr[j] trở thành i (tức là đảo ngược vị trí: giá trị tại chỉ số i trở thành chỉ số, và giá trị tại chỉ số đó trở thành i).

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

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

Đầu ra: Mảng trước khi sắp xếp: 3 4 1 2 0
Mảng sau khi sắp xếp sao cho arr[j] thành i nếu arr[i] là j: 4 2 3 0 1

Giải thích: Mảng kích thước 5, các phần tử nhỏ hơn 5. Quá trình đảo ngược:
arr[1] = 4 → arr[4] = 1; arr[2] = 1 → arr[1] = 2; arr[3] = 2 → arr[2] = 3; arr[4] = 0 → arr[0] = 4. Kết quả: 4 2 3 0 1.

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

Đầu ra: Mảng trước khi sắp xếp: 2 0 1 3
Mảng sau khi sắp xếp: 1 2 0 3

Giải thích: arr[0] = 2 → arr[2] = 0; arr[1] = 0 → arr[0] = 1; arr[2] = 1 → arr[1] = 2; arr[3] = 3 → arr[3] = 3. Kết quả: 1 2 0 3.

Phương pháp tiếp cận

• Nhập mảng số nguyên và tính kích thước.
• In mảng ban đầu, gọi hàm Rearrangement(arr, size).
• Trong hàm Rearrangement:
  • Tạo mảng phụ ptr[] cùng kích thước.
  • Vòng lặp i từ 0 đến size-1: gán ptr[arr[i]] = i.
  • Vòng lặp i từ 0 đến size-1: gán arr[i] = ptr[i].
• In mảng kết quả.

Ví dụ mã C++

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

void Rearrangement(int arr[], int size) {
    int ptr[size];
    for (int i = 0; i < size; i++) {
        ptr[arr[i]] = i;
    }
    for (int i = 0; i < size; i++) {
        arr[i] = ptr[i];
    }
}

int main() {
    int arr[] = {3, 4, 1, 2, 0};
    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 of an array such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Đầu ra chương trình

Array before Arrangement: 3 4 1 2 0
Rearrangement of an array such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: 4 2 3 0 1