โปรแกรม C++ หาจำนวนการสลับน้อยที่สุดเพื่อจัดกลุ่ม 1 ให้อยู่ติดกัน

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

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

ตัวอย่าง

ถ้าอาร์เรย์อินพุต = {1, 0, 1, 1, 0, 1} ต้องการ 1 การสลับ คือ สลับ 0 ตัวแรกกับ 1 ตัวสุดท้าย

อัลกอริทึม

• นับจำนวน 1 ทั้งหมดในอาร์เรย์
• ถ้าจำนวนคือ x เราต้องหาซับอาร์เรย์ที่มีความยาว x ของอาร์เรย์นี้ที่มี 1 มากที่สุด
• การสลับขั้นต่ำที่จำเป็นจะเป็นจำนวน 0 ในซับอาร์เรย์ที่มีความยาว x ที่มี 1 มากที่สุด

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

#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;
}

ผลลัพธ์

Minimum swap count = 1