양수와 음수를 모두 포함하는 정수 유형 배열이 제공됩니다. 예를 들어 주어진 크기의 arr[]입니다. 작업은 모든 양수 및 음수가 다른 위치에 있어야 하고 추가 양수 또는 음수 요소가 있는 경우 배열 끝에 배치되도록 배열을 재배열하는 것입니다.
여기에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다 -
입력 - 정수 arr[] ={4, 2, -1, -1, 6, -3}
출력 − O(n) 시간 및 O(1) 추가 공간에서 양수 및 음수 재배열:2 - 1 6 -1 4 -3
설명 - 양수 요소와 음수 요소를 모두 포함하는 크기 6의 정수 배열이 제공됩니다. 이제 모든 양수 요소와 음수 요소가 대체 위치에 있고 모든 추가 요소가 배열 끝에 추가되는 방식으로 배열을 재정렬합니다. 즉, 2 -1 6 -1 4 -3 최종 결과
입력 - 정수 arr[] ={-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
출력 − O(n) 시간 및 O(1) 추가 공간에서 양수 및 음수 재배열은 다음과 같습니다. 2 - 2 3 -5 5 -3 5 -1 1 3 1 1
설명 - 양수 요소와 음수 요소를 모두 포함하는 크기 12의 정수 배열이 제공됩니다. 이제 모든 양수 요소와 음수 요소가 대체 위치에 있고 모든 추가 요소가 배열의 끝에 추가되는 방식으로 배열을 재정렬합니다. 즉 2 -2 3 -5 5 -3 5 -1 1 3 1 1이 최종 결과가 됩니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수형 요소의 배열을 입력하고 배열의 크기를 계산합니다.
-
FOR 루프를 사용하여 재정렬 작업을 수행하기 전에 배열을 인쇄하십시오.
-
배열과 배열의 크기를 매개변수로 전달하여 재정렬(arr, size) 함수를 호출합니다.
-
Rearrangement(arr, size)
함수 내부-
임시 정수 유형 변수(예:temp는 -1, 양수는 temp + 1, 음수는 0)를 선언합니다.
-
i에서 0까지 루프를 시작하여 i가 배열 크기보다 작아질 때까지 반복합니다. 루프 내부에서 IF arr[i]가 0보다 작은지 확인한 다음 temp를 1씩 증가시키고 C++ STL의 내장 메서드(예:swap(arr[temp], arr[i]))를 호출하고 arr[temp] 및 arr[i를 전달합니다. ] 매개변수로.
-
WHILE 양수는 배열 크기보다 작고 음수는 양수보다 작으며 arr[음수]는 0보다 작습니다. 루프 내에서 arr[negative] 및 arr[positive]를 매개변수로 전달하여 스왑을 호출합니다. 양수를 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;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3