C++で配列の中央値を最大化する

N個の要素の配列arr[]とK

入力配列が{1、3、2、5}でk =3の場合、-

• ソートされた配列は{1、2、3、5}になります
• 5より大きい3つの要素を挿入します。この操作の後、配列は{1、2、3、5、6、6、6}になります。
• 新しいアレイの中央値は5です

アルゴリズム

1. In order to maximize the median of the resultant array, all the elements that need to be inserted must be greater than the maximum element from the array
2. Sort the array and the median of the array will be arr[size / 2] if the size is odd else (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