คำชี้แจงปัญหา
กำหนดอาร์เรย์ของจำนวนเต็ม n ที่มีเพียง 0 และ 1 ค้นหาการสลับขั้นต่ำ (สวิตช์จาก 0 เป็น 1 หรือในทางกลับกัน) ที่จำเป็นเพื่อให้อาร์เรย์นั้นถูกแบ่งพาร์ติชั่น กล่าวคือ มี 0 วินาทีแรกแล้ว 1 วินาที
ตัวอย่าง
หาก arr[] ={1, 0, 0, 1, 1, 1, 0} จำเป็นต้องมีการสลับ 2 ครั้ง เช่น สลับอันแรกและศูนย์สุดท้าย
อัลกอริทึม
- หากเราสังเกตคำถาม เราจะพบว่ามีจุดตั้งแต่ 0 ถึง n-1 โดยที่องค์ประกอบทั้งหมดที่เหลือจากจุดนั้นควรมี 0 ทั้งหมด และจากขวาไปจุดควรมี 1 ทั้งหมด
- ดัชนีที่ไม่ปฏิบัติตามกฎหมายนี้จะต้องถูกลบออก แนวคิดคือการนับ 0 ทั้งหมดจากซ้ายไปขวา
ตัวอย่าง
#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;
} เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Minimum toggles = 2
