C++で配列内の重複しない（ユニークな）要素の積を求める方法

重複する要素を含む配列が与えられたとき、その配列内で重複していない（ユニークな）要素をすべて掛け合わせた積を求めて結果を表示するのが、本記事の課題です。

例

入力: arr[] = {2, 1, 1, 2, 3, 4, 5, 5 }
出力: 120
説明: 1、2、5は複数回出現するため、最初の出現のみを考慮します。
したがって結果は 1 × 2 × 3 × 4 × 5 = 120 となります。

入力: arr[] = {1, 10, 9, 4, 2, 10, 10, 45, 4 }
出力: 32400
説明: 10と4は複数回出現するため、最初の出現のみを考慮します。
したがって結果は 1 × 10 × 9 × 4 × 2 × 45 = 32400 となります。

プログラムで使用するアプローチ

• 重複する要素を含む配列を入力として受け取る
• どの要素が重複しているかを判別しやすくするため、要素を昇順にソートしておく方法も有効（ソート済みなら隣接する同じ要素をスキップできる）
• 本実装では unordered_set（ハッシュセット）を使って出現済みの要素を記録し、初めて出現した要素だけを積に掛けていく
• 配列内のすべての重複しない要素の積として最終結果を表示する

アルゴリズム

開始
ステップ 1 → 配列内の重複しない要素の積を求める関数を宣言する
    int find_Product(int arr[], int size)
    int prod = 1 を宣言して初期化する
    unordered_set<int> s を作成する
    ループ: i = 0 から i < size まで i++ ずつ
        IF s.find(arr[i]) == s.end() ならば
            prod *= arr[i]
            s.insert(arr[i]) を呼び出す
        End
    End
    prod を返す
ステップ 2: main() 内で
    int arr[] = { 2, 1, 1, 2, 3, 4, 5, 5 } を宣言する
    配列のサイズを計算する: int size = sizeof(arr) / sizeof(int)
    find_Product(arr, size) を呼び出す
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 重複しない要素の積を計算する関数
int find_Product(int arr[], int size) {
    int prod = 1;
    unordered_set<int> s;
    for (int i = 0; i < size; i++) {
        if (s.find(arr[i]) == s.end()) {
            prod *= arr[i];
            s.insert(arr[i]);
        }
    }
    return prod;
}
int main() {
    int arr[] = { 2, 1, 1, 2, 3, 4, 5, 5 };
    int size = sizeof(arr) / sizeof(int);
    cout<<"重複しないすべての要素の積 : "<<find_Product(arr, size);
    return 0;
}

出力

重複しないすべての要素の積 : 120

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量は O(n) です。unordered_set による検索・挿入は平均 O(1) で行えるため、配列を一度走査するだけで積を求められます。要素数が多い配列でも効率的に処理できる点が、この手法の大きな利点です。