使用 C++，在 O(1) 的额外空间内重新排列数组，使得 arr[i] 变成 arr[arr[i]]

给定一个正整数类型的数组，例如 arr[]，大小任意，数组中的元素值必须大于 0 且小于数组的大小。任务是重新排列数组，使得 arr[i] 在给定的 O(1) 空间内变成 arr[arr[i]]，并打印最终结果。

让我们看看这个的不同输入输出场景 -

输入 - int arr[] = {0 3 2 1 5 4 }

输出 - 数组排列前：0 3 2 1 5 4 在 O(1) 的额外空间内重新排列数组，使得 arr[i] 变成 arr[arr[i]] 是：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 在 O(1) 的额外空间内重新排列数组，使得 arr[i] 变成 arr[arr[i]] 是：0 1

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

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

输出 - 数组排列前：1 0 2 3 在 O(1) 的额外空间内重新排列数组，使得 arr[i] 变成 arr[arr[i]] 是：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 开始循环，直到 i 小于 size。在循环内部，将 temp 设置为 arr[arr[i]] % size，并将 arr[i] 加上 temp * size。

    • 从 i 为 0 开始循环，直到 i 小于 size。在循环内部，将 arr[i] 设置为 arr[i] / size

  • 打印结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

Open Compiler
#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

更新于： 2021年11月2日

744 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告