C++에서는 O(n) 시간 복잡도와 O(1) 추가 공간으로 양수와 음수를 재배열합니다.

우리는 주어진 크기의 arr[]과 같이 양수와 음수를 포함하는 정수형 배열을 얻습니다. 이 작업은 모든 양수와 음수가 교대로 위치해야 하고 추가 양수 또는 음수가 있는 경우 배열을 다시 정렬하는 것입니다. 요소는 배열의 끝에 배치됩니다.

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

input − int arr[] = {4, 2, -1, -1, 6, -3}

output− O(n) 시간과 O(1) 시간의 추가 공간의 음수는 다음과 같습니다: 2 - 1 6 -1 4 -3

Explanation− 양수 및 음수 요소를 포함하는 크기 6의 정수 배열을 얻습니다. 이제 모든 양수 요소가 합산되도록 배열을 재정렬하겠습니다. 음수 요소는 대체 위치에 있으며 모든 추가 요소는 배열 끝에 추가됩니다. 즉, 2 -1 6 -1 4 -3이 최종 결과가 됩니다.

input

input

Strong>− int arr [] = {- 1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

output strong>− O(n) 시간 및 O(1) 추가 공백과 음수는 다음과 같이 재배열됩니다: 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Explanation - 양수 및 음수 요소를 포함하는 크기 12의 정수 배열을 얻습니다. 이제 모든 양수 요소와 음수 요소가 교대로 위치하고 모든 추가 요소가 배열의 끝에 추가되도록 배열을 다시 정렬하겠습니다. 즉, 최종 요소의 경우 2 -2 3 -5 5 -3 5 -1 1 3 1 1입니다. 결과

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

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

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

• 배열과 배열 크기를 인수로 전달하여 Rearrangement(arr, size) 함수를 호출하세요.

• 함수 내부적으로 재정렬(arr, size)

  • 임시 정수 변수를 선언합니다. 즉, temp는 -1, 양수는 temp + 1, 음수는 0입니다.

  • i가 배열 크기보다 작아질 때까지 i에서 0까지 반복을 시작합니다. 루프 내에서 IF arr[i]가 0보다 작은지 확인한 다음 temp를 1씩 증가시키고 C++ STL의 내장 메서드인 swap(arr[temp], arr[i])를 호출하고 arr[temp를 전달합니다. ] 및 arr[i]를 매개변수로 사용합니다.

  • 루프를 시작합니다. 양수가 배열 크기보다 작고 음수가 양수보다 작고 arr[음수]가 0보다 작은 경우. 루프 내에서 arr[negative] 및 arr[plus]를 인수로 전달하여 호출을 교환합니다. 양수에 1을 더하고 음수를 음수 + 2로 설정합니다.

• 결과를 인쇄하세요.

예

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int temp = -1;
   for(int i = 0; i < size; i++){
      if (arr[i] < 0){
         temp++;
         swap(arr[temp], arr[i]);
      }
   }
   int positive = temp + 1;
   int negative = 0;
   while(positive < size && negative < positive && arr[negative] < 0){
      swap(arr[negative], arr[positive]);
      positive++;
      negative = negative + 2;
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

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

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

위 내용은 C++에서는 O(n) 시간 복잡도와 O(1) 추가 공간으로 양수와 음수를 재배열합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!