จัดเรียงอาร์เรย์ให้ arr[j] กลายเป็น i หาก arr[i] เป็น j ใน C++

เราได้รับอาร์เรย์จำนวนเต็มบวกขนาดใดก็ตาม ซึ่งค่าของสมาชิกในอาร์เรย์จะมากกว่า 0 แต่น้อยกว่าขนาดของอาร์เรย์ งานคือจัดเรียงอาร์เรย์ใหม่เพื่อให้ หาก arr[j] = j แล้ว arr[j] จะกลายเป็น i และแสดงผลลัพธ์สุดท้าย (กล่าวคือ สลับตำแหน่ง index กับ value)

ตัวอย่างการทำงาน (Input/Output)

ตัวอย่างที่ 1

Input: int arr[] = {3, 4, 1, 2, 0}

Output: 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

คำอธิบาย: อาร์เรย์ขนาด 5 มีค่าทุกตัวน้อยกว่า 5 การจัดเรียงใหม่คือ: arr[1]=4 → arr[4]=1; arr[2]=1 → arr[1]=2; arr[3]=2 → arr[2]=3; arr[4]=0 → arr[0]=4 ดังนั้นอาร์เรย์สุดท้ายคือ 4 2 3 0 1

ตัวอย่างที่ 2

Input: int arr[] = {2, 0, 1, 3}

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

คำอธิบาย: อาร์เรย์ขนาด 4 การจัดเรียง: arr[0]=2 → arr[2]=0; arr[1]=0 → arr[0]=1; arr[2]=1 → arr[1]=2; arr[3]=3 → arr[3]=3 ผลลัพธ์คือ 1 2 0 3

อัลกอริทึมที่ใช้

• รับอาร์เรย์จำนวนเต็มและคำนวณขนาด
• พิมพ์อาร์เรย์ก่อนจัดเรียง และเรียกฟังก์ชัน Rearrangement(arr, size)
• ภายในฟังก์ชัน Rearrangement(arr, size):
  • สร้างอาร์เรย์ช่วย ptr[] ขนาดเท่ากับ arr[]
  • วนลูป for จาก i = 0 ถึง size-1 กำหนด ptr[arr[i]] = i
  • วนลูป for จาก i = 0 ถึง size-1 กำหนด arr[i] = ptr[i]
• พิมพ์อาร์เรย์หลังจัดเรียงใหม่

ตัวอย่างโค้ด 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;
}

ผลลัพธ์

การรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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