C++에서는 O(1) 추가 공간을 사용하여 양수 항목과 음수 항목이 교대로 배열되도록 배열을 재정렬합니다.

우리는 주어진 크기의 arr[]과 같이 양수와 음수를 포함하는 정수형 배열을 얻습니다. 이 작업은 양수가 음수로 둘러싸이도록 배열을 재배열하는 것입니다. 좀 더 긍정적이고 긍정적인 마음이 있었다면 음수는 배열의 끝 부분에 정렬됩니다.

다양한 입력 및 출력 상황을 살펴보겠습니다. −

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

Output − 정렬 전 배열: -1 -2 -3 1 2 3 양수 항목과 음수 항목이 번갈아 표시되고 추가 공간이 필요하지 않도록 배열을 다시 정렬하는 방법은 -1 1 -2 2 -3 3입니다.

Explanation: 양수 요소와 음수 요소를 포함하는 크기 6의 정수 배열이 제공됩니다. 이제 추가 공간을 요구하지 않고 모든 양수 요소가 음수 요소 앞에 나타나도록 배열을 재정렬하겠습니다. 음수 요소와 모든 추가 요소로 둘러싸인 -1 1 -2 2 -3 3은 최종 결과인 최종 배열의 끝에 추가됩니다.

Input - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

Output - 배열을 정렬하기 전 : -1 -2 -3 1 2 3 5 5 -5 3 1 1 추가 공간을 사용하지 않고 양수와 음수를 번갈아 배열하여 배열을 재배열하는 시간 복잡도는 O(1): -1 1 -2 2 -3 3 -5 5 5 3 1 1

Explanation - An 정수를 제공합니다. 양수 요소와 음수 요소를 포함하는 크기 12의 배열입니다. 이제 모든 양수 요소가 음수 요소로 둘러싸여 있도록 배열을 재정렬하고 모든 추가 요소를 배열 끝에 추가합니다. 즉, -1 1 -2 2 -3 3 -5 5 5 3 1 1이 최종 결과.

아래 프로그램에서 사용한 방법은 다음과 같습니다

• 정수형 배열을 입력하고 배열의 크기를 계산해 보세요.

• 재배열 작업을 수행하기 전에 FOR 루프를 사용하여 배열을 인쇄하세요.

• 배열과 배열 크기를 매개변수로 전달하여 함수 재정렬(arr, size)을 호출합니다.

• 재정렬(arr, size) 함수 내에서

  • 정수 변수 'ptr'을 선언하고 -1로 초기화합니다.

  • i가 크기보다 작아질 때까지 i에서 0까지 반복합니다. 루프 내에서 ptr이 0보다 큰지 확인한 다음 arr[i]가 0보다 크고 arr[ptr]가 0보다 작은지 또는 arr[i]가 0보다 작고 arr[ptr]가 0보다 큰지 확인합니다. 그런 다음 move_array(arr, size, ptr, i) 함수를 호출하고 i - ptr이 2보다 큰지 확인한 다음 ptr을 ptr + 2로 설정합니다. 그렇지 않으면 ptr을 -1로 설정하십시오.

  • ptr이 -1인지 확인한 다음 arr[i]가 0보다 크고 !(i & 0x01) 또는 (arr[i]가 0보다 작음) 및 (i & 0x01)을 확인한 다음 설정합니다. 나에게 ptr을 줘.

• move_array(int arr[], int size, int ptr, int temp)

  • 함수 내에서 'ch'라는 문자 유형 변수를 선언하고 arr[temp]로 설정합니다.

  • i가 ptr보다 커질 때까지 i에서 temp까지 반복합니다. 루프 내에서 arr[i]를 arr[i - 1]로 설정합니다.

  • arr[ptr]을 ch로 설정합니다.

예제

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   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 in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

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

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

위 내용은 C++에서는 O(1) 추가 공간을 사용하여 양수 항목과 음수 항목이 교대로 배열되도록 배열을 재정렬합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!