我们得到一个正整数类型数组,比方说,任意给定大小的 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。
输入− 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。
下面程序中使用的方法如下
-
输入一个整型元素数组,计算数组大小
-
打印排列前的数组,调用函数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