ソート済み配列における絶対値の異なる要素数を数える方法

この記事では、配列内の要素のうち、絶対値が異なる要素がいくつあるかを数える方法を解説します。例えば、配列に {5, 5, 6, -5, 8, 2, -2, 1} という8つの要素が含まれているとします。しかし、絶対値で見ると {5, 6, 8, 2, 1} の5種類しか存在しません。-5 と 5 は符号が異なるだけで、絶対値としては同じ値であるため、別々の要素とはみなされません。

この問題を解決するには、Set（セット）データ構造を利用するのが効果的です。セットには重複した要素を格納できないという特性があります。そこで、配列の各要素をセットに挿入する際に、絶対値に変換してから挿入することで、自動的に重複が排除されます。

アルゴリズム

absoluteDistinctCount(arr)

begin
    define set s;
    for each element e in arr, do
        insert |e| into s
    done
    return the number of elements of s
end

アルゴリズムの流れ

1. 空のセット s を定義します。
2. 配列 arr の各要素 e について、その絶対値 |e| をセット s に挿入します。
3. 最後に、セット s の要素数を返します。これが絶対値の異なる要素の個数となります。

実装例（C++）

#include<iostream>
#include<set>
#include<cmath>
using namespace std;
int absoluteDistinctCount(int arr[], int n){
    set<int> s;
    for(int i = 0; i<n; i++){
        s.insert(abs(arr[i])); // 絶対値を挿入
    }
    return s.size();
}
main() {
    int arr[] = {5, 5, 6, -5, 8, 2, -2, 1};
    int n = (sizeof(arr))/(sizeof(arr[0]));
    cout << "Absolute Distinct Count: " << absoluteDistinctCount(arr, n);
}

実行結果

Absolute Distinct Count: 5

計算量について

このアルゴリズムの時間計算量は O(n log n) です。各要素のセットへの挿入には O(log n) の時間がかかり、それを n 個の要素に対して行うためです。空間計算量は O(n) となり、最悪の場合すべての要素がセットに格納されます。

なお、配列がすでにソートされている場合は、セットを使わずに両端からポインタを移動させながら比較する手法（Two Pointers テクニック）を用いることで、O(n) の時間計算量・O(1) の空間計算量で解くことも可能です。