C++で2つのソート済み配列をマージしてK番目の要素を求める方法

このチュートリアルでは、2つのソート済み配列をマージ（統合）した配列から、K番目の要素を見つけるプログラムをC++で作成します。

まず、問題を解くための手順を確認しましょう。

• 2つのソート済み配列を初期化します。
• サイズ m + n の空の配列を用意します。
• 2つの配列を新しい配列にマージします。
• マージ後の配列から k - 1 番目の要素を返します。

このアルゴリズムは、マージソートの要領で2つの配列の先頭同士を比較しながら小さい方を順に格納していくことで、全体をソートされた状態で統合できるのがポイントです。マージ処理の計算量は O(m + n) となります。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <iostream>
using namespace std;
int findKthElement(int arr_one[], int arr_two[], int m, int n, int k) {
   int sorted_arr[m + n];
   int i = 0, j = 0, index = 0;
   while (i < m && j < n) {
      if (arr_one[i] < arr_two[j]) {
         sorted_arr[index++] = arr_one[i++];
      }else {
         sorted_arr[index++] = arr_two[j++];
      }
   }
   while (i < m) {
      sorted_arr[index++] = arr_one[i++];
   }
   while (j < n) {
      sorted_arr[index++] = arr_two[j++];
   }
   return sorted_arr[k - 1];
}
int main() {
   int arr_one[5] = {1, 3, 5, 7, 9}, arr_two[5] = {2, 4, 6, 8, 10};
   int k = 7;
   cout << findKthElement(arr_one, arr_two, 5, 4, k) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

7

この例では、{1, 3, 5, 7, 9} と {2, 4, 6, 8, 10} をマージすると {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} となり、7番目の要素である「7」が出力されます。

まとめ

本記事では、2つのソート済み配列をマージしてK番目の要素を取得する方法を解説しました。配列を実際に統合するシンプルなアプローチは理解しやすく、マージソートの仕組みの復習にも最適です。チュートリアルについて質問がある場合は、コメント欄でお知らせください。