C++でK個の要素を追加した後の中央値を求める方法

この記事では、n個の整数からなる配列が与えられ、そこにK個の要素を追加した後の配列の中央値を求める問題について解説します。なお、追加後の要素数「N + K」は奇数であるという条件が前提となっています。

問題の概要

具体的な例を使って、問題を理解しましょう。

入力

array = {23, 65, 76, 67} ; k = 1

出力

67

この場合、元の配列に1つの要素を追加した結果の配列に対する中央値として「67」が出力されます。

解法のアプローチ

この問題を解く手順は以下の通りです。

1. まず、与えられた配列の要素を昇順にソートします。
2. 次に、配列の末尾にk個の要素を追加することを想定します。これは、追加される要素が既存のどの要素よりも大きい値になることを意味します。

ここで重要なのは、「N + K が奇数」という条件です。要素数が奇数の場合、中央値はちょうど真ん中の位置にある要素となるため、次の式で計算できます。

(n + K) / 2

つまり、ソート済みの配列において、インデックス (n + K) / 2 の位置にある要素がそのまま答えになります。追加される要素はすべて最大値より大きいため、中央値の位置は元の配列内の要素と一致します。

C++での実装例

それでは、実際に中央値を求めるプログラムを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int findMedianAfterK(int arr[], int n, int K) {
   sort(arr, arr + n);
   return arr[((n + K)/2)];
}
int main() {
   int array[] = {3,56, 8, 12, 67, 10 };
   int k = 3;
   int n = sizeof(array) / sizeof(array[0]);
   cout<<"The median after adding "<<k<<" elements is "<<findMedianAfterK(array, n, k);
   return 0;
}

実行結果

The median after adding 3 elements is 56

コードの解説

• findMedianAfterK関数：まず sort() を使って配列を昇順に並べ替え、その後インデックス (n + K) / 2 の要素を返します。
• main関数：サンプル配列 {3, 56, 8, 12, 67, 10}（要素数6）に k = 3 を加えると、合計要素数は9（奇数）となり、中央値の位置は 9 / 2 = 4 となります。ソート後の配列は {3, 8, 10, 12, 56, 67} なので、インデックス4の要素「56」が中央値として出力されます。

このように、ソートと単純なインデックス計算だけで効率的に中央値を求められるのが、このアルゴリズムのポイントです。計算量はソート処理が支配的となり、O(n log n) で完了します。