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

配列（Array）とは、同じデータ型の要素を集めたデータ構造のことです。ソート済み配列とは、要素が昇順または降順に並べられた配列を指します。

異なる要素数（distinct count）とは、配列内に重複して存在しない要素の数のことです。

絶対値の異なる要素数（absolute distinct count）とは、各要素の絶対値（符号を無視した値）に着目したときの、異なる要素の数を意味します。

この記事では、ソート済み配列における絶対値の異なる要素数を求めるプログラムを紹介します。つまり、配列の各要素の絶対値を考えた場合に、何種類の値が存在するかをカウントします。

例を見てみましょう。

入力 : [-3, 0, 3, 6]
出力 : 3

この配列には「0」「3」「6」という3つの異なる絶対値が存在します。-3と3は符号が異なるだけで絶対値は同じため、1つとしてカウントされます。

この問題を解くには、主に2つの方法があります。それぞれ詳しく見ていきましょう。

方法1：set（集合）を使う

setは常に重複しない要素のみを保持するコンテナです。この特性を利用し、各要素の絶対値をsetに挿入していき、最終的なsetのサイズを返すことで、異なる絶対値の数を求めることができます。

アルゴリズム

• 配列と同じデータ型のsetを作成します。

• 各要素の絶対値を求め、setに格納します。同じ値が複数回現れても、setには1つの値のみが保存されます。

• すべての要素を挿入し終えたら、setのサイズを返します。これが配列内の異なる絶対値の数となります。

コード例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int arr[] = {-3, 0, 2, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "絶対値の異なる要素数 : ";
    unordered_set<int> s;
    for (int i = 0 ; i < n; i++)
        s.insert(abs(arr[i]));
    int nof = s.size();
    cout << nof;
    return 0;
}

出力

絶対値の異なる要素数 : 4

この方法は実装が非常にシンプルで分かりやすいのが特徴です。ただし、setに要素を格納するためO(n)の追加メモリが必要になる点に注意しましょう。

方法2：配列の走査とカウント変数を使う

この方法では、setのような追加コンテナを使わず、単一のカウント変数のみで解きます。配列がソート済みであることを利用し、両端から2つのポインタを動かしながら、絶対値が等しい要素（符号だけが異なる要素）や重複要素を検出してカウントを調整していきます。

コード例

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-5, -1, 0, 5, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "絶対値の異なる要素数 : ";
    int count = n;
    int i = 0, j = n - 1, sum = 0;
    while (i < j) {
        while (i != j && arr[i] == arr[i + 1])
            count--, i++;
        while (i != j && arr[j] == arr[j - 1])
            count--, j--;
        if (i == j)
            break;
        sum = arr[i] + arr[j];
        if (sum == 0) {
            count--;
            i++, j--;
        }
        else if(sum < 0)
            i++;
        else
            j--;
    }
    cout << count;
    return 0;
}

出力

絶対値の異なる要素数 : 4

この例では、-5と5が絶対値として等しいため1つにまとめられ、{-5, -1, 0, 5, 8}の5要素から4という結果が得られます。

まとめ

setを使う方法はコードが簡潔で理解しやすい一方、追加メモリを消費します。一方、両端から走査する方法は追加メモリをほとんど必要とせず、ソート済み配列という前提条件を活かした効率的なアプローチです。配列のサイズやメモリ制約に応じて、適切な方法を選択しましょう。