重新排列一个数组，使得arr变为arr]，并且只使用O(1)额外的空间，使用C++实现

我们得到一个正整数类型数组，比方说，任意给定大小的 arr[]，这样数组中的元素值应大于 0 但小于数组的大小。任务是重新排列 一个数组，仅在给定的 O(1) 空间内将 arr[i] 变为 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。

立即学习“C++免费学习笔记（深入）”；

输入− 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。

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

• 输入一个整型元素数组，计算数组大小

  

  Pi智能演示文档

  领先的AI PPT生成工具

  下载

• 打印排列前的数组，调用函数Rearrangement (arr, size)

• 函数内部重排(arr, size)

  • 开始循环FOR from i 到 0 直到 i 小于大小。在循环内部，将 temp 设置为 arr[arr[i]] % size 和 arr[i] += temp * size。

  • 开始循环 FOR 从 i 到 0 直到 i小于尺寸。在循环内，设置 arr[i] = arr[i] / size

• 打印结果。

示例

#include 
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