在C++中重新排列数组,使得如果`arr[i]`为`j`,则`arr[j]`变为`i`


给定一个正整数类型的数组,例如`arr[]`,大小任意,数组中的元素值大于0小于数组大小。任务是重新排列数组,使得如果`arr[j]`为`j`,则`arr[j]`变为`i`,并打印最终结果。

让我们看看各种输入输出场景:

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

输出 - 排序前数组:3 4 1 2 0 重新排列数组使得如果arr[i]是j,则arr[j]变为i的结果是:4 2 3 0 1

解释 - 我们得到一个大小为5的整数数组,所有数组元素的值都小于5。现在,我们将重新排列数组,即`arr[1]`是4,`arr[4] = 1`;`arr[2]`是1,`arr[1] = 2`;`arr[3]`是2,`arr[2] = 3`;`arr[4]`是0,`arr[0] = 4`。因此,最终数组是4 2 3 0 1。

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

输出 - 排序前数组:2 0 1 3 重新排列数组使得如果arr[i]是j,则arr[j]变为i的结果是:1 2 0 3

解释 - 我们得到一个大小为4的整数数组,所有数组元素的值都小于4。现在,我们将重新排列数组,即`arr[0]`是2,`arr[2] = 0`;`arr[1]`是0,`arr[0] = 1`;`arr[2]`是1,`arr[1] = 2`;`arr[3]`是3,`arr[3] = 3`。因此,最终数组是1 2 0 3。

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

  • 输入一个整数类型的数组,并计算数组的大小。

  • 打印排序前的数组,并调用函数`Rearrangement(arr, size)`

  • 在函数`Rearrangement(arr, size)`内部:

    • 创建一个与数组`arr[]`大小相同的整数类型数组`ptr[]`。

    • 开始FOR循环,从`i = 0`到`i < size`。在循环内,设置`ptr[arr[i]] = i`。

    • 开始FOR循环,从`i = 0`到`i < size`。在循环内,设置`arr[i] = ptr[i]`。

  • 打印重新排列数组值后的数组。

示例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int ptr[size];
   for(int i = 0; i < size; i++){
      ptr[arr[i]] = i;
   }
   for(int i = 0; i < size; i++){
      arr[i] = ptr[i];
   }
}
int main(){
   //input an array
   int arr[] = {3, 4, 1, 2, 0};
   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 such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

输出

如果我们运行上述代码,它将生成以下输出

Array before Arrangement: 3 4 1 2 0
Rearrangement of an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ is: 4 2 3 0 1

更新于:2021年11月2日

233 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告