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 sao cho tất cả các số dương và âm phải ở các vị trí thay thế và nếu có thêm các phần tử dương hoặc âm thì chúng sẽ được đặt ở 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 [] ={4, 2, -1, -1, 6, -3}
Đầu ra - Sắp xếp lại các số dương và số âm trong O (n) thời gian và O (1) khoảng trống dư là:2 - 1 6 -1 4 -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 sao cho tất cả các phần tử dương và các phần tử âm ở vị trí thay thế và tất cả các phần tử thừa sẽ được thêm vào cuối mảng, tức là 2 -1 6 -1 4 -3 sẽ là kết quả cuối cùng
Đầu vào - int arr [] ={-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
Đầu ra - Sắp xếp lại các số dương và số âm trong O (n) thời gian và O (1) khoảng trống dư là:2 - 2 3 -5 5 -3 5 -1 1 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 sao cho tất cả các phần tử dương và các phần tử âm ở vị trí thay thế 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à 2 -2 3 -5 5 -3 5 -1 1 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 các biến kiểu số nguyên tạm thời, tức là tăng đến -1, dương thành tạm thời + 1 và âm thành 0.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước của một mảng. Bên trong vòng lặp, kiểm tra IF arr [i] nhỏ hơn 0, sau đó tăng nhiệt độ lên 1 và gọi phương thức có sẵn của C ++ STL, tức là swap (arr [temp], arr [i]) và truyền arr [temp] và arr [i ] như một tham số.
-
Bắt đầu vòng lặp WHILE dương nhỏ hơn kích thước của một mảng AND âm nhỏ hơn kích thước dương AND arr [âm] nhỏ hơn 0. Bên trong vòng lặp, gọi hoán đổi bằng cách chuyển arr [âm] và arr [dương] làm tham số. Tăng số dương lên 1 và đặt âm thành âm + 2.
-
-
In kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3