Đề bài
Cho mảng các 0 và 1. Nhiệm vụ tìm số lần hoán vị tối thiểu để gom tất cả 1 có mặt trong mảng lại với nhau.
Ví dụ
Nếu mảng đầu vào = {1, 0, 1, 1, 0, 1} thì cần 1 lần hoán vị. Tức hoán vị 0 đầu tiên với 1 cuối cùng.
Thuật toán
- Đếm tổng số 1 trong mảng
- Nếu đếm được x, cần tìm mảng con độ dài x của mảng này có số 1 nhiều nhất
- Số hoán vị tối thiểu sẽ là số 0 trong mảng con độ dài x có số 1 nhiều nhất
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMinSwaps(int *arr, int n) { int oneCnt = 0; for (int i = 0; i < n; ++i) { if (arr[i] == 1) { ++oneCnt; } } int x = oneCnt; int maxOnes = INT_MIN; int preCompute[n] = {0}; if (arr[0] == 1) { preCompute[0] = 1; } for (int i = 1; i < n; ++i) { if (arr[i] == 1) { preCompute[i] = preCompute[i - 1] + 1; } else { preCompute[i] = preCompute[i - 1]; } } for (int i = x - 1; i < n; ++i) { if (i == (x - 1)) { oneCnt = preCompute[i]; } else { oneCnt = preCompute[i] - preCompute[i - x]; } if (maxOnes < oneCnt) { maxOnes = oneCnt; } } int swapCnt = x - oneCnt; return swapCnt; } int main() { int arr[] = {1, 0, 1, 1, 0, 1}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum swap count = 1