Tuyên bố vấn đề
Cho một mảng 0 và 1. Nhiệm vụ là tìm số lượng hoán đổi tối thiểu cần thiết để nhóm tất cả cá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ì 1 lần hoán đổi là bắt buộc. tức là hoán đổi 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 số đếm là x, thì chúng ta cần tìm mảng con có độ dài x của mảng này với số lượng lớn nhất là 1's
- Số lần hoán đổi tối thiểu bắt buộc sẽ là số lượng 0 trong mảng con có độ dài x với số lượng tối đa là 1
Ví dụ
#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 bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Đầu ra
Minimum swap count = 1