우리는 배열의 요소가 0보다 크고 배열 크기보다 작은 값을 가져야 하는 임의의 주어진 크기의 arr[]와 같은 양의 정수 유형 배열이 제공됩니다. 주어진 O(1) 공간에서만 arr[i]가 arr[arr[i]]가 되도록 배열을 재배열하고 최종 결과를 출력하는 것이 과제입니다.
여기에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다 -
입력 - 정수 arr[] ={0 3 2 1 5 4 }
출력 - 배열 전 배열:0 3 2 1 5 4arr[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.
입력 - 정수 arr[] ={1, 0}
출력 − 배열 전 배열:1 0arr[i]가 arr[arr[i]]가 되도록 배열을 재정렬하고 O(1) 추가 공간은 다음과 같습니다. 0 1
설명 - 우리는 크기가 2인 정수 배열과 2보다 작은 배열 값이 주어진다. 이제 배열을 재정렬할 것이다. 즉, arr[arr[0]은 1이고 arr[arr[1]]은 0이다. 그래서 , 재정렬 후 최종 배열은 0 1입니다.
입력 - 정수 arr[] ={1, 0, 2, 3}
출력 − 배열 전 배열:1 0 2 3arr[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)
-
Rearrangement(arr, size)
함수 내부-
i에서 크기보다 작아질 때까지 FOR 루프를 시작합니다. 루프 내에서 temp를 arr[arr[i]] % size 및 arr[i] +=temp * size로 설정합니다.
-
i에서 크기보다 작아질 때까지 FOR 루프를 시작합니다. 루프 내에서 arr[i] =arr[i] / size
를 설정합니다.
-
-
결과를 인쇄하십시오.
예시
#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