Chúng ta được cung cấp một mảng kiểu số nguyên chứa cả số dương và số âm, giả sử arr [] có kích thước bất kỳ. Nhiệm vụ là sắp xếp lại một mảng theo cách mà sẽ có một số dương sẽ được bao quanh bởi các số âm. Nếu có nhiều số âm và dương hơn, thì chúng sẽ được sắp xếp ở cuối một mảng.
Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -
Đầu vào - int arr [] ={-1, -2, -3, 1, 2, 3}
Đầu ra - Mảng đứng trước Sắp xếp:-1 -2 -3 1 2 3 Sắp xếp lại một mảng theo các mục âm và dương xen kẽ với O (1) khoảng trống thừa là:-1 1 -2 2 -3 3
Giải thích - chúng ta được cho một mảng số nguyên có kích thước 6 chứa cả phần tử dương và âm. Bây giờ, chúng ta sẽ sắp xếp lại mảng theo cách mà tất cả các phần tử dương sẽ được bao quanh bởi các phần tử âm và tất cả các phần tử thừa sẽ được thêm vào cuối một mảng, tức là -1 1 -2 2 -3 3 sẽ là phần tử cuối cùng kết quả.
Đầu vào - int arr [] ={-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};
Đầu ra - Mảng đứng trước Sắp xếp:-1 -2 -3 1 2 3 5 5 -5 3 1 1 Sắp xếp lại một mảng trong các mục âm &dương xen kẽ với O (1) khoảng trống thừa là:-1 1 -2 2 -3 3 -5 5 5 3 1 1
Giải thích - chúng ta được cho một mảng số nguyên kích thước 12 chứa cả phần tử dương và âm. Bây giờ, chúng ta sẽ sắp xếp lại mảng theo cách mà tất cả các phần tử dương sẽ được bao quanh bởi các phần tử âm và tất cả các phần tử thừa sẽ được thêm vào cuối một mảng, tức là -1 1 -2 2 -3 3 -5 5 5 3 1 1 sẽ là kết quả cuối cùng.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một mảng các phần tử kiểu số nguyên và tính kích thước của một mảng.
-
In một mảng trước khi thực hiện hành động sắp xếp lại bằng vòng lặp FOR.
-
Gọi đến hàm Sắp xếp lại (arr, size) bằng cách chuyển mảng và kích thước của mảng dưới dạng tham số.
-
Bên trong chức năng Sắp xếp lại (arr, size)
-
Khai báo một biến số nguyên ‘ptr’ và khởi tạo nó bằng -1.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước. Bên trong vòng lặp, kiểm tra IF ptr lớn hơn 0 rồi kiểm tra IF arr [i] lớn hơn 0 VÀ arr [ptr] nhỏ hơn 0 HOẶC arr [i] nhỏ hơn 0 VÀ arr [ptr] lớn hơn 0 rồi gọi hàm move_array (arr, size, ptr, i) và kiểm tra NẾU i - ptr lớn hơn 2 rồi đặt ptr thành ptr + 2. ELSE, đặt ptr thành -1.
-
Kiểm tra IF ptr thành -1 rồi kiểm tra arr [i] lớn hơn 0 AND! (I &0x01) OR (arr [i] nhỏ hơn 0) AND (i &0x01) rồi đặt ptr thành i.
-
-
Bên trong hàm move_array (int arr [], int size, int ptr, int temp)
-
Khai báo một biến dưới dạng ký tự kiểu ‘ch’ và đặt nó bằng arr [temp].
-
Bắt đầu vòng lặp FOR từ tôi đến nhiệt độ cho đến khi tôi lớn hơn ptr. Bên trong vòng lặp, đặt arr [i] với arr [i - 1].
-
Đặt arr [ptr] thành ch.
-
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
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