จัดเรียงอาร์เรย์ให้ arr[i] กลายเป็น arr[arr[i]] ด้วยพื้นที่ O(1) ใน C++

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

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

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

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

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

คำอธิบาย: อาร์เรย์ขนาด 6 arr[arr[0]]=0, arr[arr[1]]=1, arr[arr[2]]=2, arr[arr[3]]=3, arr[arr[4]]=4, arr[arr[5]]=5 ผลลัพธ์คือ 0 1 2 3 4 5

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

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

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

คำอธิบาย: อาร์เรย์ขนาด 2 arr[arr[0]]=1, arr[arr[1]]=0 ผลลัพธ์คือ 0 1

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

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

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

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

อัลกอริทึมที่ใช้ (Technique: Encoding Two Values in One)

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

ตัวอย่างโค้ด 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 of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

ผลลัพธ์

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

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