จำนวนสมาชิกน้อยที่สุดที่ต้องเพิ่มเพื่อทำให้มัธยฐานเท่ากับ x ด้วย C++

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

กำหนดอาร์เรย์ "arr" ขนาด n และสมาชิก x งานคือหาจำนวนสมาชิกน้อยที่สุดที่ต้องเพิ่มในอาร์เรย์เพื่อทำให้มัธยฐาน (Median) เท่ากับ x

มัธยฐานในอาร์เรย์ที่มีความยาว n คือสมาชิกที่ครอบครองตำแหน่งหมายเลข (n-1)/2 หลังจากเราจัดเรียงสมาชิกในลำดับไม่ลดลง (Non-decreasing) ตัวอย่างเช่น ในอาร์เรย์ด้านล่าง มัธยฐานคือ 20 -

arr1[] = {10, 20, 30, 40}

ถ้า arr[] = {1, 2, 3} และ x = 4 แล้วเราต้องเพิ่ม 4 ตัวคือ {4, 5, 5, 5} ในอาร์เรย์เพื่อทำให้มัธยฐานเท่ากับ 4

อัลกอริทึม

อัลกอริทึมมีความเรียบง่ายมาก เราต้องเพิ่มตัวเลข x เข้าไปในอาร์เรย์จนกว่ามัธยฐานของอาร์เรย์จะเท่ากับ x

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

#include <iostream>
#include <algorithm>
using namespace std;

int minNumbersToBeAdded(int *arr, int n, int x) {
    sort(arr, arr + n);
    int cnt = 0;
    while (arr[(n - 1)/2] != x) {
        arr[n] = x;
        ++n;
        sort(arr, arr + n);
        ++cnt;
    }
    return cnt;
}

int main() {
    int arr[20] = {1, 2, 3};
    int x = 4;
    int n = 3;
    cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum numbers to be added = 4