โปรแกรม C++ หาจำนวนการสลับน้อยที่สุดเพื่อแบ่งอาร์เรย์ไบนารีให้เป็น 0 ก่อน 1 หลัง

ข้อความโจทย์

กำหนดอาร์เรย์ของ n จำนวนเต็มที่มีเฉพาะ 0 และ 1 หาจำนวนการสลับ (เปลี่ยนจาก 0 เป็น 1 หรือในทางกลับกัน) น้อยที่สุดที่จำเป็น เพื่อให้อาร์เรย์ถูกแบ่งพาร์ติชัน กล่าวคือ มี 0 ก่อน แล้วตามด้วย 1

ตัวอย่าง

ถ้า arr[] = {1, 0, 0, 1, 1, 1, 0} ต้องการ 2 การสลับ คือ สลับ 1 ตัวแรกและ 0 ตัวสุดท้าย

อัลกอริทึม

• หากเราสังเกตโจทย์ จะพบว่าจะมีจุดที่แน่นอนจาก 0 ถึง n-1 ที่องค์ประกอบทั้งหมดทางซ้ายของจุดนั้นควรเป็น 0 ทั้งหมด และทางขวาควรเป็น 1 ทั้งหมด
• ดัชนีที่ไม่ปฏิบัติตามกฎนี้จะต้องถูกลบออก แนวคิดคือนับ 0 ทั้งหมดจากซ้ายไปขวา

ตัวอย่างโค้ด C++

#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