เพิ่ม Median ของอาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ขนาด N และจำนวนเต็ม K โดย K < N งานคือแทรก K จำนวนเต็มเข้าไปในอาร์เรย์เดิม เพื่อให้ Median ของอาร์เรย์ผลลัพธ์มีค่าสูงสุด

ถ้าอินพุตอาร์เรย์คือ {1, 3, 2, 5} และ k = 3

• อาร์เรย์เรียงแล้ว: {1, 2, 3, 5}
• แทรก 3 ตัวที่มากกว่า 5 อาร์เรย์กลายเป็น {1, 2, 3, 5, 6, 6, 6}
• Median ของอาร์เรย์ใหม่คือ 5

อัลกอริทึม

1. เพื่อเพิ่ม Median ให้มากที่สุด องค์ประกอบที่แทรกทั้งหมดต้องมากกว่าค่าสูงสุดของอาร์เรย์เดิม
2. จัดเรียงอาร์เรย์ Median จะเป็น arr[size/2] ถ้าขนาดคี่ ไม่งั้น (arr[(size/2)-1] + arr[size/2]) / 2

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

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

double getMaxMedian(int* arr, int n, int k) {
    int newSize = n + k;
    double median;
    sort(arr, arr + n);
    if (newSize % 2 == 0) {
        median = (arr[(newSize / 2) - 1] + arr[newSize / 2]) / 2;
        return median;
    }
    median = arr[newSize / 2];
    return median;
}

int main() {
    int arr[] = {1, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Max median = " << getMaxMedian(arr, n, k) << endl;
    return 0;
}

ผลลัพธ์

Max median = 5