C++で指定された要素を削除した後の最大値を求める方法

問題概要

サイズnの整数型配列arr[]と、削除したい要素を格納したサイズmの配列del[]が与えられます。求めたいのは、arr[]からdel[]に含まれる要素をすべて取り除いた後に残る、最大の要素の値です。

なお、削除対象の要素が配列内に複数存在する場合でも、削除するのは最初に出現した1つだけである点に注意してください。

入出力例

入力 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}
出力 : 7

解説:

要素を削除した後の配列 arr[] : {5, 7, 2}
この配列の最大値は 7

解法1: ソートを利用するシンプルなアプローチ

最も分かりやすいのは、以下の手順で処理を行う方法です。

1. arr[]の各要素について、del[]に同じ値が存在するかを確認する。
2. 存在すれば、その要素(最初のインスタンス)をINT_MAXで上書きし、「削除済み」の目印にする。
3. 配列全体を昇順にソートする。
4. ソート後の配列において、削除済み要素(INT_MAX)を除いた末尾の要素、すなわちarr[n-m-1]が答えとなる。

削除判定にO(n×m)、ソートにO(n log n)を要するため、全体の計算量はO(n×m + n log n)です。

実装例

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

int findMaxElementDelArray(int arr[], int n, int del[], int m){
   // 削除対象の要素をINT_MAXで上書き(最初の1つだけ)
   for(int i = 0; i < m; i++){
      for(int j = 0; j < n; j++){
         if(arr[j] == del[i]){
            arr[j] = INT_MAX;
            break;
         }
      }
   }
   sort(arr, arr + n);
   return arr[(n - m - 1)];
}

int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int m = sizeof(del) / sizeof(del[0]);
   cout<<"削除後の最大要素は "<<findMaxElementDelArray(array, n, del, m);
   return 0;
}

出力

削除後の最大要素は 7

解法2: ハッシュマップを利用する効率的なアプローチ

より高速に処理したい場合は、unordered_map(ハッシュマップ)を活用しましょう。手順は次のとおりです。

1. del[]の全要素をハッシュマップdelMapに登録し、各値の出現回数をカウントしておく。
2. arr[]を先頭から走査し、各要素がdelMapに存在するかを確認する。
3. 存在する場合は削除対象なので、対応するカウントを1減らす。カウントが0になったらキーごと削除する。
4. 存在しない場合は有効な要素なので、現在の最大値maxValと比較し、大きければ更新する。
5. 走査が終わった時点のmaxValが、削除後の配列における最大値となる。

ハッシュマップへの検索・挿入は平均O(1)で行えるため、この方法の計算量はO(n + m)となり、解法1より大幅に高速です。

実装例

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

int findMaxElementDelArray(int arr[], int n, int del[], int m){
   unordered_map<int, int> delMap;
   // 削除対象の要素を出現回数付きで登録
   for (int i = 0; i < m; ++i) {
      delMap[del[i]]++;
   }
   int maxVal = INT_MIN;
   for (int i = 0; i < n; ++i) {
      if (delMap.find(arr[i]) != delMap.end()) {
         // 削除対象ならカウントを減らし、0になったら消す
         delMap[arr[i]]--;
         if (delMap[arr[i]] == 0)
            delMap.erase(arr[i]);
      }
      else
         maxVal = max(maxVal, arr[i]);
   }
   return maxVal;
}

int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int m = sizeof(del) / sizeof(del[0]);
   cout<<"削除後の最大要素は "<<findMaxElementDelArray(array, n, del, m);
   return 0;
}

出力

削除後の最大要素は 7

まとめ

指定された要素を削除した後の最大値を求める問題では、ソートを使う方法がシンプルで理解しやすい一方、計算量はO(n×m + n log n)になります。ハッシュマップを使えば削除対象の判定を高速化でき、全体をO(n + m)で処理可能です。データ量が多い場合やパフォーマンスが重要な場面では、ハッシュマップを活用するアプローチを選ぶとよいでしょう。