C++で素数の配列から重複要素を削除するプログラムの実装方法

サイズNの配列が与えられ、そのすべての要素が素数であるとします。この課題は、与えられた配列の中から重複する要素を見つけ出し、それらを削除することです。具体的な例を見てみましょう。

入力例1 −

N = 8
arr[ ] = { 2, 2, 2, 3, 3, 3, 5, 7 }

出力 −

2 3 5 7

説明 − 与えられた素数の配列には「2」と「3」の重複が含まれています。これらの重複を削除すると、出力は 2 3 5 7 となります。

入力例2 −

N = 5
arr[ ] = { 3, 2, 7, 5, 5 }

出力 −

3 2 7 5

説明 − 与えられた素数の配列には「5」の重複が含まれています。重複を削除すると、出力は 3 2 7 5 となります。

この問題を解くためのアプローチ

この問題では、各数値がすでに出現した（訪問済み）かどうかを記録するためのフラグ配列を使用します。配列の要素がまだ訪問されていない場合は、フラグを「1」に設定して結果に挿入し、すでに訪問済みの場合は挿入を行いません。

• 要素を含むサイズNのベクター配列を入力として受け取ります。

• 整数型ベクターを返す関数 removeDuplicates(vector<int>&arr, int size) を定義し、配列とそのサイズを引数として渡します。

• 現在の要素が訪問済みかどうかを判定するための整数配列を用意します。挿入の際に、ある要素がすでに訪問済み（フラグが「1」）であれば、その要素をベクターに追加せず、未訪問であれば要素をベクター配列にプッシュします。

• 最終的な結果のベクターには、重複のない一意な素数のみが格納されます。

実装例

#include<bits/stdc++.h>
using namespace std;

vector<int> removeDuplicates(vector<int>& arr, int size){
    int num[100] = {0};
    vector<int> vec;
    for(int i = 0; i < size; i++){
        if(num[arr[i]] == 0){
            num[arr[i]] = 1;
            vec.push_back(arr[i]);
        }
    }
    return vec;
}

int main(){
    int N = 8;
    vector<int> arr = {2, 2, 2, 3, 3, 3, 5, 7};
    vector<int> answer = removeDuplicates(arr, N);
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

2 3 5 7

重複を削除した結果、出力は 2 3 5 7 となります。

計算量について

このアプローチでは、配列を一度だけ走査するため、時間計算量はO(N)です。また、フラグ配列として固定サイズの補助配列を使用しているため、空間計算量もO(N)となります。要素の出現順序を保持したい場合に特に有効な手法です。