使用 C++ 重新排列一个数组，以便 arr[i] 变为 arr[arr[i]] 并且 O(1) 额外空间

我们得到一个正整数类型数组，比方说，任何给定大小的arr[]，这样数组中的元素的值应该大于0但小于数组的大小。任务是以这样的方式重新排列数组，使得arr[i]仅在给定的O(1)空间内变为arr[arr[i]]并打印最终结果。

让我们看看这个的各种输入输出场景-

输入 -intarr[]={032154}

输出 -排列前的数组：032154重新排列数组，使arr[i]变为arr[arr[i]]并具有O(1)额外空间：012345

解释 -我们得到一个大小为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。因此，重排后的最终数组为012345。

输入 -intarr[]={1,0}

输出 -排列前的数组：10重新排列数组，使arr[i]变为arr[arr[i]]，O(1)额外空间为：01

解释-我们得到一个大小为2的整数数组，数组中的所有元素都小于2。现在，我们将重新排列数组，即arr[arr[0]为1，arr[arr[1]]为0。因此，重排后的最终数组为01。

输入 -intarr[]={1,0,2,3}

输出 -排列前的数组：1023重新排列数组，使arr[i]变为arr[arr[i]]，O(1)额外空间为：0123

解释-我们给定一个大小为4的整数数组，数组中的所有元素都小于4。现在，我们将重新排列数组，即arr[arr[0]为0，arr[arr[1]]为1，arr[arr[2]]为2，arr[arr[3]]为3。因此，重排后的最终数组为0123。

下面程序中使用的方法如下

输入整数类型元素的数组并计算数组的大小

排列前打印数组并调用函数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