C++で絶対差が1以下となる要素の最大数を求める方法

n個の要素からなる配列が与えられたとします。この配列から、選んだ任意の2つの要素の絶対差が1以下になるように、最大でいくつの要素を選べるかを求める問題です。例えば、配列が [2, 2, 3, 4, 5] の場合、答えは3となり、要素数が最大となる組み合わせは「2, 2, 3」です。

解法の考え方

絶対差が0または1であるということは、選べる数値は「x」と「x + 1」の2種類に限られることを意味します。そこで、各要素の出現回数(頻度)を記録しておき、隣り合う2つの値の頻度の合計が最大になるところを探せば、それが求める答えとなります。

アルゴリズムの手順

1. mapを使って、配列内の各要素の出現回数をカウントする
2. 各キーkeyについて、key+1がマップ内に存在するかどうかを確認する
3. 存在する場合は occurrence[key] + occurrence[key+1] を計算し、現在の最大値より大きければ更新する
4. 最終的な最大値を答えとして返す

サンプルコード(C++)

#include <iostream>
#include <map>
using namespace std;
int maxElem(int arr[], int n) {
    map<int,int> occurrence;
    for(int i=0;i<n;++i){
        if(occurrence[arr[i]])
            occurrence[arr[i]] += 1;
        else
            occurrence[arr[i]] = 1;
    }
    int ans = 0, key;
    map<int,int>:: iterator it=occurrence.begin();
    while(it!=occurrence.end()) {
        key = it->first;
        ++it;
        if(occurrence[key+1]!=0)
        ans=max(ans,occurrence[key]+occurrence[key+1]);
    }
    return ans;
}
int main(){
    int arr[] = {2, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Result is: " << maxElem(arr, n);
}

実行結果

Result is: 3

計算量について

このアルゴリズムでは、まず配列を一度走査して頻度マップを作成します。std::mapへの挿入はO(log n)かかるため、ここでの計算量はO(n log n)です。その後、マップ内の各キーに対して定数時間の処理を行うため、全体の時間計算量はO(n log n)、空間計算量はO(n)となります。なお、順序が不要な場合はunordered_mapを使うことで、平均O(n)まで高速化できます。