Trong bài toán này, chúng ta được cung cấp một mảng và nhiệm vụ của chúng ta là chuyển đổi mảng sao cho tất cả các số dương ở vị trí chỉ số chẵn và tất cả các số âm đều ở vị trí chỉ số lẻ.
Có thể có một số lượng giá trị âm và dương không bằng nhau, trong trường hợp này, chúng tôi sẽ không di chuyển các giá trị phụ.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - {3, 5, -1, 19, -7, -2}
Đầu ra - {3, -1, 5, -7, 19, -2}
Để giải quyết vấn đề này, chúng ta sẽ phải tìm phần tử không có thứ tự trong mảng. Có thể có nhiều hơn một cách để tìm ra điều này, ở đây chúng ta sẽ thảo luận về hai trong số chúng.
Phương pháp 1
Phương thức này sẽ chỉ đơn giản là duyệt qua mảng và tìm lần xuất hiện đầu tiên của các phần tử không ở đúng vị trí (tức là dương không ở chẵn và âm không phải atodd) và sau đó hoán đổi chúng. Chúng tôi sẽ thực hiện quá trình này cho đến khi toàn bộ mảng được duyệt qua.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
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
Phương pháp 2
Trong phương pháp này, chúng tôi sẽ sử dụng một quy trình giống như một loại kỹ thuật nhanh chóng. Ở đây, chúng ta sẽ lấy hai con trỏ, một cho số dương và một cho số âm. Chúng tôi sẽ đặt con trỏ tích cực tại chỉ số 0 (chỉ số chẵn) và tiêu cực tại chỉ số 1 (chỉ số lẻ). Và bước tiếp con trỏ bằng 2. Và dừng lại khi con trỏ dương gặp số âm và con trỏ âm gặp số dương. Và sau đó hoán đổi khi cả hai dừng lại. Nếu bất kỳ con trỏ nào đi ra ngoài chỉ mục mảng, chúng tôi sẽ ngừng thực thi.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi
#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;
} Đầu ra
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