Cho mảng nguyên arr[] chứa số dương và âm. Nhiệm vụ: sắp xếp mảng sao cho nếu phần tử nhỏ nhất là lẻ thì xếp theo thứ tự lẻ-chẵn-lẻ-chẵn...; nếu nhỏ nhất là chẵn thì chẵn-lẻ-chẵn-lẻ... Nếu số lượng lẻ/chẵn nhiều hơn thì điền 0 vào chỗ trống.
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {1, 1, 2, 2, 5, 4}
Đầu ra - Sắp xếp lẻ chẵn xen kẽ tăng dần: 1 2 1 2 5 4.
Giải thích - Phần tử nhỏ nhất là 1 (lẻ) → xếp lẻ trước, chẵn sau: 1 2 1 2 5 4.
Đầu vào - int arr[] = {6, 3, 2, 8, 10, 4}
Đầu ra - Sắp xếp lẻ chẵn xen kẽ tăng dần: 2 3 4 0 6 0
Giải thích - Phần tử nhỏ nhất là 2 (chẵn) → xếp chẵn trước, lẻ sau. Số chẵn nhiều hơn lẻ → điền 0.
Phương pháp sử dụng trong chương trình dưới đây
Nhập mảng, tính size. Sắp xếp mảng bằng sort STL.
Gọi Rearrangement(arr, size).
Trong Rearrangement:
Tạo vector vec_1 (chẵn), vec_2 (lẻ).
int temp=0, bool check=false.
Duyệt mảng: nếu arr[i]%2==0 push vec_1, else push vec_2.
i=0, j=0. Nếu arr[0]%2==0 → check=true.
While temp < size: nếu check → arr[temp++] = vec_1[i++], check=!check; else arr[temp++] = vec_2[j++], check=!check.
In kết quả.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; void Rearrangement(int arr[], int size){ vector<int> vec_1, vec_2; int temp = 0; bool check = false; for(int i = 0; i < size; i++){ if(arr[i] % 2 == 0){ vec_1.push_back(arr[i]); } else{ vec_2.push_back(arr[i]); } } int i = 0; int j = 0; if(arr[0] % 2 == 0){ check = true; } while(temp < size){ if(check == true){ arr[temp++] = vec_1[i++]; check = !check; } else{ arr[temp++] = vec_2[j++]; check = !check; } } } int main(){ int arr[] = { 1, 1, 2, 2, 5, 4 }; int size = sizeof(arr) / sizeof(int); sort(arr, arr + size); cout<<"Sắp xếp lẻ chẵn xen kẽ tăng dần: "; Rearrangement(arr, size); 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ả:
Sắp xếp lẻ chẵn xen kẽ tăng dần: 1 2 1 2 5 4