เราได้รับอาร์เรย์ประเภทจำนวนเต็มบวก สมมติว่า arr[] ของขนาดที่กำหนดใดๆ เพื่อให้องค์ประกอบในอาร์เรย์มีค่ามากกว่า 0 แต่น้อยกว่าขนาดของอาร์เรย์ งานคือการจัดเรียงอาร์เรย์ใหม่ในลักษณะที่ arr[i] กลายเป็น arr[arr[i]] ภายในพื้นที่ O(1) ที่กำหนดเท่านั้น และพิมพ์ผลลัพธ์สุดท้าย
ให้เราดูสถานการณ์อินพุตเอาต์พุตที่หลากหลายสำหรับสิ่งนี้ -
ป้อนข้อมูล − int arr[] ={0 3 2 1 5 4 }
ผลผลิต − Array before Arrangement:0 3 2 1 5 4 การจัดเรียงอาร์เรย์ใหม่เพื่อให้ arr[i] กลายเป็น arr[arr[i]] โดยมี O(1) ช่องว่างเพิ่มเติมคือ:0 1 2 3 4 5
คำอธิบาย − เราได้รับอาร์เรย์จำนวนเต็มขนาด 6 และองค์ประกอบทั้งหมดในค่าอาร์เรย์ที่น้อยกว่า 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.
ป้อนข้อมูล − int arr[] ={1, 0}
ผลผลิต − Array before Arrangement:1 0การจัดเรียงอาร์เรย์ใหม่เพื่อให้ arr[i] กลายเป็น arr[arr[i]] โดยมีพื้นที่พิเศษ O(1) คือ 0 1
คำอธิบาย − เราได้รับอาร์เรย์จำนวนเต็มขนาด 2 และองค์ประกอบทั้งหมดในค่าอาร์เรย์ที่น้อยกว่า 2 ตอนนี้ เราจะจัดเรียงอาร์เรย์ใหม่ เช่น arr[arr[0] คือ 1 และ arr[arr[1]] เป็น 0 ดังนั้น , อาร์เรย์สุดท้ายหลังจากการจัดเรียงใหม่คือ 0 1
ป้อนข้อมูล − int arr[] ={1, 0, 2, 3}
ผลผลิต − Array before Arrangement:1 0 2 3Rearrangement ของอาร์เรย์เพื่อให้ arr[i] กลายเป็น arr[arr[i]] โดยเว้นวรรค O(1) คือ 0 1 2 3
คำอธิบาย − เราได้รับอาร์เรย์จำนวนเต็มขนาด 4 และองค์ประกอบทั้งหมดในค่าอาร์เรย์ที่น้อยกว่า 4 ตอนนี้ เราจะจัดเรียงอาร์เรย์ใหม่ เช่น arr[arr[0] คือ 0, arr[arr[1]] คือ 1, arr [arr[2]] คือ 2 และ arr[arr[3]] คือ 3 ดังนั้น อาร์เรย์สุดท้ายหลังจากการจัดเรียงใหม่คือ 0 1 2 3
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ป้อนอาร์เรย์ขององค์ประกอบประเภทจำนวนเต็มและคำนวณขนาดของอาร์เรย์
-
พิมพ์อาร์เรย์ก่อนจัดเรียงและเรียกใช้ฟังก์ชัน Rearrangement(arr, size)
-
ภายในฟังก์ชัน การจัดเรียงใหม่ (arr, size)
-
เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าขนาด ภายในลูป ตั้งค่า temp เป็น arr[arr[i]] % size และ arr[i] +=temp * size.
-
เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าขนาด ภายในลูป ตั้งค่า arr[i] =arr[i] / size
-
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#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(){
//input an array
int arr[] = {0, 3, 2, 1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
//print the original Array
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
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
