我们得到一个正整数类型数组，比方说，任何给定大小的 arr[] ，这样数组中的元素的值应该大于 0 但小于数组的大小。任务是以这样的方式重新排列数组，使得 arr[i] 仅在给定的 O(1) 空间内变为 arr[arr[i]] 并打印最终结果。
输入 - int arr[] = {0 3 2 1 5 4 }
输出 - 排列前的数组：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}
输出 - 排列前的数组：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}
输出 - 排列前的数组：1 0 2 3 重新排列数组，使 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)
函数内部 Rearrangement(arr, size)
从 i 到 0 开始循环 FOR，直到 i 小于 size。在循环内，将 temp 设置为 arr[arr[i]] % size 和 arr[i] += temp * size。
从 i 到 0 开始循环 FOR，直到 i 小于 size。在循环内，设置 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(){
//输入一个数组
int arr[] = {0, 3, 2, 1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
//打印原始数组
cout<<"排列前的数组： ";
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;
}输出结果如果我们运行上面的代码，它将生成以下输出
排列前的数组： 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