이 문제에서 배열이 주어지고 우리의 임무는 모든 양수가 짝수 인덱스 위치에 있고 모든 음수가 홀수 인덱스 위치에 있도록 배열을 변환하는 것입니다.
양수 값과 음수 값의 수가 같지 않을 수 있으며 이 경우 추가 값을 이동하지 않습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - {3, 5, -1, 19, -7, -2}
출력 - {3, -1, 5, -7, 19, -2}
이 문제를 해결하려면 배열에서 순서가 잘못된 요소를 찾아야 합니다. 이것을 찾는 방법이 한 가지 이상 있을 수 있습니다. 여기서는 그 중 두 가지에 대해 설명하겠습니다.
방법 1
이 방법은 단순히 배열을 순회하고 제자리에 없는 요소의 첫 번째 발생을 찾은 다음(즉, 짝수가 아닌 양수와 atodd가 아닌 음수) 교체합니다. 전체 배열이 순회될 때까지 이 프로세스를 수행합니다.
예시
솔루션 구현을 보여주는 프로그램,
#include<iostream>
using namespace std;
void swapElements(int* a, int i , int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return ;
}
void printArray(int* a, int n){
for(int i = 0; i<n; i++)
cout<<a[i]<<"\t";
cout<<endl;
return ;
}
void generateOrderedArray(int arr[], int n){
for(int i = 0; i <n; i++){
if(arr[i] >= 0 && i % 2 == 1){
for(int j = i + 1; j <n; j++){
if(arr[j] < 0 && j % 2 == 0){
swapElements(arr, i, j);
break ;
}
}
}
else if(arr[i] < 0 && i % 2 == 0){
for(int j = i + 1; j <n; j++){
if(arr[j] >= 0 && j % 2 == 1){
swapElements(arr, i, j);
break;
}
}
}
}
printArray(arr, n);
}
int main(){
int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Inital Array is : ";
printArray(arr, n);
cout<<"Array with positive numbers at even index and negative numbers at odd index :";
generateOrderedArray(arr,n);
return 0;
} 출력
Inital Array is : 3 5 -1 19 -7 -2 Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2
방법 2
이 방법에서는 일종의 빠른 기술처럼 보이는 프로세스를 사용합니다. 여기서 우리는 두 개의 포인터를 사용할 것입니다. 하나는 양수이고 다른 하나는 음수입니다. 인덱스 0(짝수 인덱스)에 양수 포인터를 설정하고 인덱스 1(홀수 인덱스)에 음수 포인터를 설정합니다. 그리고 포인터를 2만큼 앞으로 이동합니다. 그리고 양수 포인터가 음수를 만나고 음수 포인터가 양수를 만나면 멈춥니다. 그리고 둘 다 멈출 때 교환하십시오. 포인터 중 하나라도 배열 인덱스를 벗어나면 실행을 중지합니다.
예시
솔루션 구현을 보여주는 프로그램
#include <iostream>
using namespace std;
void swapElements(int* a, int i , int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return ;
}
void printArray(int *a, int n){
for (int i = 0; i <n; i++)
cout<<a[i]<<"\t";
cout<<endl;
}
void generateOrderedArray(int a[], int size){
int positive = 0, negative = 1;
while (1) {
while (positive < size && a[positive] >= 0)
positive += 2;
while (negative <size && a[negative] <= 0)
negative += 2;
if (positive < size && negative < size)
swapElements(a, positive, negative);
else
break;
}
}
int main(){
int arr[] = { 3, 5, -1, 19, -7, -2 };
int n = (sizeof(arr) / sizeof(arr[0]));
cout<<"Inital Array is : ";
printArray(arr, n);
cout<<"Array with positive numbers at even index and negative numbers at odd index : ";
generateOrderedArray(arr, n);
printArray(arr, n);
return 0;
} 출력
Inital Array is : 3 5 -1 19 -7 -2 Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2