Cho mảng nguyên arr[] chứa số dương và âm. Nhiệm vụ: sắp xếp mảng sao cho số dương bị bao quanh bởi số âm (âm-dương-âm...). Phần dư đẩy về cuối.
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {-1, -2, -3, 1, 2, 3}
Đầu ra - Mảng trước: -1 -2 -3 1 2 3. Sắp xếp xen kẽ dương âm O(1): -1 1 -2 2 -3 3
Giải thích - Mảng size 6. Số dương được bao quanh bởi âm: -1 1 -2 2 -3 3.
Đầu vào - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
Đầu ra - Mảng trước: -1 -2 -3 1 2 3 5 5 -5 3 1 1. Sắp xếp xen kẽ dương âm O(1): -1 1 -2 2 -3 3 -5 5 5 3 1 1
Giải thích - Mảng size 12. Kết quả: -1 1 -2 2 -3 3 -5 5 5 3 1 1.
Phương pháp sử dụng trong chương trình dưới đây
Nhập mảng, tính size.
In mảng trước.
Gọi Rearrangement(arr, size).
Trong Rearrangement:
int ptr = -1.
For i=0..size-1:
Nếu ptr>=0 và ((arr[i]>=0 && arr[ptr]<0) || (arr[i]<0 && arr[ptr]>=0)) → gọi move_array(arr, size, ptr, i).
Nếu i-ptr>=2 → ptr+=2; else ptr=-1.
Nếu ptr==-1 và ((arr[i]>=0 && !(i&0x01)) || (arr[i]<0 && (i&0x01))) → ptr=i.
Hàm move_array(arr, size, ptr, temp): ch = arr[temp]; for i=temp downto ptr+1: arr[i]=arr[i-1]; arr[ptr]=ch.
Ví dụ mã
#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(){ int arr[] = {-1, -2, -3, 1, 2, 3}; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Mảng trước: "; for (int i = 0; i < size; i++){ cout << arr[i] << " "; } Rearrangement(arr, size); cout<<"\nSắp xếp xen kẽ dương âm O(1): "; for(int i = 0; i < size; i++){ cout<< arr[i] << " "; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Mảng trước: -1 -2 -3 1 2 3 Sắp xếp xen kẽ dương âm O(1): -1 1 -2 2 -3 3