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

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

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

ตัวอย่าง

ถ้าอาร์เรย์อินพุตคือ = {1, 5, 4, 7, 2, 10} และ k = 6 ต้องการ 1 การสลับ คือ สลับองค์ประกอบ 7 กับ 2

อัลกอริทึม

• นับองค์ประกอบทั้งหมดที่น้อยกว่าหรือเท่ากับ 'k' ให้จำนวนเป็น 'cnt'
• ใช้เทคนิค two pointer สำหรับหน้าต่างที่มีความยาว 'cnt' ทุกครั้งติดตามว่ามีองค์ประกอบกี่ตัวในช่วงนี้ที่มากกว่า 'k' ให้จำนวนรวมเป็น 'outOfRange'
• ทำซ้ำขั้นตอนที่ 2 สำหรับทุกหน้าต่างที่มีความยาว 'cnt' และเลือกค่าต่ำสุดของจำนวน 'outOfRange' ระหว่างพวกเขา นี่จะเป็นคำตอบสุดท้าย

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

#include <bits/stdc++.h>
using namespace std;

int getMinSwaps(int *arr, int n, int k) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= k) {
            ++cnt;
        }
    }
    int outOfRange = 0;
    for (int i = 0; i < cnt; ++i) {
        if (arr[i] > k) {
            ++outOfRange;
        }
    }
    int result = outOfRange;
    for (int i = 0, j = cnt; j < n; ++i, ++j) {
        if (arr[i] > k) {
            --outOfRange;
        }
        if (arr[j] > k) {
            ++outOfRange;
        }
        result = min(result, outOfRange);
    }
    return result;
}

int main() {
    int arr[] = {1, 5, 4, 7, 2, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum swaps = " << getMinSwaps(arr, n, k) << endl;
    return 0;
}

ผลลัพธ์

Minimum swaps = 1