C++で配列の全要素を同じ値にするための最小削除操作数を求めるアルゴリズム

問題概要

n個の要素からなる配列が与えられます。要素には重複が含まれる場合があります。この配列から任意の数の要素を削除できるとき、すべての要素を同じ値にするために必要な最小の削除数を求めるのが課題です。

例として、次の配列を考えてみましょう。

arr[] = {10, 8, 10, 7, 10, -1, -4, 12}

この場合、最も多く出現している「10」以外の5つの要素を削除すれば、配列の全要素を10で統一できます。つまり、答えは5回の削除となります。

解法の考え方

この問題の鍵となるのは、「削除する量を最小化する = 残す要素の数を最大化する」という発想です。全要素を同じ値にするためには、必ずどれか1つの値だけを残すことになります。したがって、出現回数が最も多い要素を残し、それ以外をすべて削除すればよいことになります。

アルゴリズム

1. 各要素の出現回数（頻度）をカウントする
2. 頻度の中から最大値を求める（maxFrequencyとする）
3. 削除が必要な要素数 = n − maxFrequency（nは配列のサイズ）

頻度のカウントにはハッシュマップ（unordered_map）を使うと、平均O(1)でアクセスでき、全体の計算量はO(n)に抑えられます。

C++での実装例

#include <iostream>
#include <unordered_map>
#include <climits>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
using namespace std;

int minDeleteOperations(int *arr, int n){
    unordered_map<int, int> frequency;
    int maxFrequency = INT_MIN;

    // 各要素の出現回数をカウント
    for (int i = 0; i < n; ++i) {
        frequency[arr[i]]++;
    }

    // 最大の出現回数を求める
    for (auto it = frequency.begin(); it != frequency.end(); ++it) {
        maxFrequency = max(maxFrequency, it->second);
    }

    // 全体のサイズから最大頻度を引いたものが最小削除数
    return (n - maxFrequency);
}

int main(){
    int arr[] = {10, 8, 10, 7, 10, -1, 9, 4};
    cout << "必要な削除回数: " << minDeleteOperations(arr, SIZE(arr)) << "\n";
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

必要な削除回数: 5

計算量について

• 時間計算量: O(n) — 配列を一度走査して頻度をカウントし、マップ内のエントリを走査して最大値を求めます。
• 空間計算量: O(k) — kは配列内の異なる要素の種類数です。

このように、ハッシュマップを活用することで、効率的かつシンプルに最小削除操作数を求めることができます。