Tuyên bố vấn đề
Cho một mảng n số nguyên chỉ chứa 0 và 1. Tìm các chuyển đổi tối thiểu (chuyển từ 0 sang 1 hoặc ngược lại) được yêu cầu để mảng trở thành phân vùng, tức là nó có các số 0 đầu tiên sau đó đến 1s.
Ví dụ
Nếu arr [] ={1, 0, 0, 1, 1, 1, 0} thì bắt buộc phải có 2 chuyển đổi, tức là chuyển đổi số đầu tiên và số 0 cuối cùng.
Thuật toán
- Nếu quan sát câu hỏi, chúng tôi sẽ thấy rằng chắc chắn sẽ tồn tại một điểm từ 0 đến n-1 trong đó tất cả các phần tử còn lại đến điểm đó phải chứa tất cả các điểm 0 và điểm phải tới phải chứa tất cả các điểm 1
- Những chỉ số không tuân theo luật này sẽ phải bị xóa. Ý tưởng là đếm tất cả các số 0 từ trái sang phải.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
int zeroCnt[n + 1] = {0};
for (int i = 1; i <= n; ++i) {
if (arr[i - 1] == 0) {
zeroCnt[i] = zeroCnt[i - 1] + 1;
} else {
zeroCnt[i] = zeroCnt[i - 1];
}
}
int result = n;
for (int i = 1; i <= n; ++i) {
result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
}
return result;
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum toggles = " << getMinToggles(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 toggles = 2