在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