【C++】指定した要素を削除した後に最小値を見つける方法

この記事では、2つの配列 arr[] と del[] が与えられたときに、del[] に含まれる要素を arr[] から削除した後の最小値を見つける問題を解説します。

具体的には、arr[] の値のうち del[] にも存在するものを取り除き、削除後の配列における最小値を出力します。なお、重複した値については del[] に出現する回数分だけ削除され、それ以外は残る点に注意が必要です。

例で問題を確認しよう

入力:

arr[] = {2, 5, 6, 9, 1}
del[] = {1, 5, 9}

出力:

2

この例では、arr[] から 1・5・9 が削除されるため、残った値の中で最も小さい 2 が結果となります。

解決アプローチ：ハッシュを活用する

この問題に対するシンプルかつ効率的な解法がハッシュ（ハッシュマップ）を使う方法です。手順は以下の通りです。

• まず、del[] 配列のすべての値をハッシュテーブルに挿入します（このとき各値の出現回数もカウントしておきます）。
• 次に、arr[] を先頭から走査し、各値がハッシュテーブルに存在するかを確認します。
• 存在する場合は削除対象なのでスキップし、ハッシュ内のカウントを1減らします。カウントが0になったらエントリを削除します。
• 存在しない場合は候補となる値なので、現在の最小値（minVal）より小さければ更新します。
• 最終的に得られた minVal が答えとなります。

この手法により、重複した値を含む場合でも、指定された回数だけ正確に要素を削除することが可能です。

実装例

上記の解法の動作を示すC++プログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int findSmallestVal(int arr[], int m, int del[], int n){
    unordered_map<int, int> delVals;
    for (int i = 0; i < n; ++i) {
        delVals[del[i]]++;
    }
    int minVal = INT_MAX;
    for (int i = 0; i < m; ++i) {
        if (delVals.find(arr[i]) != delVals.end()) {
            delVals[arr[i]]--;
            if (delVals[arr[i]] == 0)
                 delVals.erase(arr[i]);
        }
        else
            minVal = min(minVal, arr[i]);
    }
    return minVal;
}
int main(){
    int array[] = { 5, 12, 33, 4, 56, 12, 20 };
    int m = sizeof(array) / sizeof(array[0]);
    int del[] = { 12, 4, 56, 5 };
    int n = sizeof(del) / sizeof(del[0]);
    cout<<"The smallest value after the deleting element is "<<findSmallestVal(array, m, del, n);
    return 0;
}

出力

The smallest value after the deleting element is 12

実行結果の解説

このサンプルコードでは、arr[] に 12 が2回登場しますが、del[] には 12 が1回しか含まれていないため、削除されるのは最初の1つだけです。したがって、削除後に残る最小値は 12 となります。このように、ハッシュで出現回数を管理することで、重複を含むケースでも正しく動作させることができます。

まとめ

本記事では、配列から指定要素を削除した後に最小値を求める問題について、ハッシュマップを利用した解法を紹介しました。時間計算量は O(m + n)（m は arr[] の要素数、n は del[] の要素数）となり、非常に効率的です。重複データの扱い方にも触れましたので、同様のアルゴリズム問題を解く際の参考にしてください。