arr이 arr]이 되도록 배열을 재정렬하고 C++로 구현된 O(1) 추가 공간만 사용합니다.

우리는 주어진 크기의 arr[]과 같은 양의 정수 유형의 배열을 얻습니다. 따라서 배열의 요소 값은 0보다 크고 배열 크기보다 작아야 합니다. 임무는 재배열이다 주어진 O(1) 공간에서 arr[i]를 arr[arr[i]]로만 변환하고 최종 결과를 인쇄하는 배열입니다.

이 상황에 대한 다양한 입력 및 출력 시나리오를 살펴보겠습니다. −

input− int arr[] = {0 3 2 1 5 4 }

output− 정렬 전 배열: 0 3 2 1 5 4 arr[i]가 arr[arr[i]]가 되도록 배열을 재정렬하고 O(1) 추가 공간: 0 1 2 3 4 5

Explanation− 크기 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입니다.

input− int arr[] = {1, 0}

output− 순열 전 배열: 1 0 arr[i]가 arr[arr[i]]가 되도록 배열을 재정렬합니다. 여기서 O(1) 추가 공간은 0 1

Explanation - 크기 2의 정수를 얻고 배열의 모든 요소는 값을 갖습니다. 2개의 배열보다 작습니다. 이제 arr[arr[0]이 1이고 arr[arr[1]]이 0이 되도록 배열을 재배열하겠습니다. 따라서 재배열 후의 최종 배열은 0 1입니다.

Input− int arr[] = {1, 0, 2, 3}

Output−정렬 전 배열: 1 0 2 3 arr[i]가 O(1) 추가 공간을 사용하여 arr[arr[i]]가 되도록 배열을 재정렬합니다. 0 1 2 3

Explanation - 크기 4의 정수 배열과 모든 요소 배열이 제공됩니다. 4보다 작은 값을 갖습니다. 이제 arr[arr[0]은 0, arr[arr[1]]은 1, arr[arr[2] ]]는 2, arr[arr[3]]은 3이 되도록 배열을 재정렬하겠습니다. 따라서 재배열 후의 최종 배열은 0 1 2 3입니다.

다음 프로그램에서 사용하는 방법은 다음과 같습니다

• 정수 요소의 배열을 입력하고 배열의 크기를 계산합니다

• 배열 전에 배열을 인쇄하고 재정렬(arr, size) 함수를 호출합니다

• 함수의 내부 재배열(arr, size)

  • i가 size보다 작을 때까지 i에서 0까지 FOR 루프를 시작합니다. 루프 내에서 temp를 arr[arr[i]] % size로 설정하고 arr[i] += temp * size로 설정합니다.

  • i가 크기보다 작아질 때까지 i에서 0까지 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;
}

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다

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

위 내용은 arr이 arr]이 되도록 배열을 재정렬하고 C++로 구현된 O(1) 추가 공간만 사용합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!