C++で配列の中央値を最大化する方法を解説

問題の概要

N個の要素を含む配列 arr[] と整数 K(K < N)が与えられます。求められているのは、この配列にK個の整数要素を挿入し、結果として得られる配列の中央値を最大化することです。

例として、入力配列が {1, 3, 2, 5}、k = 3 の場合を考えてみましょう。

• 配列をソートすると {1, 2, 3, 5} になります
• 最大値の5より大きい要素を3つ挿入します。この操作により、配列は {1, 2, 3, 5, 6, 6, 6} になります
• 新しい配列の中央値は 5 となります

アルゴリズムの考え方

この問題を解くためのポイントは、以下の2点です。

1. 挿入する要素の選び方: 中央値を最大化するには、挿入するすべての要素が元の配列の最大要素より大きくなければなりません。こうすることで、挿入された要素はすべて中央値の位置より後ろに並ぶため、元の配列の中央部分がそのまま保たれます。
2. 中央値の求め方: 配列をソートした後、新しいサイズが奇数の場合は中央値は arr[size / 2]、偶数の場合は (arr[(size / 2) - 1] + arr[size / 2]) / 2 として計算できます。

C++による実装例

#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

計算量の分析

このアルゴリズムの時間計算量は、配列のソートが支配的となるため O((N + K) log(N + K)) です。また、追加のメモリを必要としないため、空間計算量は O(1) となります。

まとめ

配列の中央値を最大化するには、最大値より大きい要素を挿入するだけでよく、複雑なデータ構造は一切不要です。ソート後に中央位置の要素を取り出すだけで答えが得られる、シンプルでありながら考え方が重要な問題といえます。