C++プログラム：配列内の各要素の最後の出現を相対的な順序で出力する方法

配列 a[] が与えられたとき、リスト内の各要素について最後に出現したものだけを出力するのが本記事の目的です。ここでは単純に重複要素を削除するだけでなく、各要素が配列内で最後に出現したタイミングに基づき、元の相対的な順序を維持したまま出力する必要があります。

例えば、6つの要素を持つ配列 {1, 3, 2, 3, 1, 2} には重複した値が含まれています。この場合、期待される結果は「3 1 2」になります。

入力例と出力例

Input: a[]={4,2,2,4,1,5,1}
Output : 2 4 5 1

この例では、「2」はインデックス2で最後に出現し、「4」はインデックス3、「5」はインデックス5、「1」はインデックス6で最後に出現しています。そのため、出力は元の順序を保ちつつ「2 4 5 1」となります。

アルゴリズム

この問題は、STLの unordered_map を使うことで効率的に解決できます。まず各要素の最後の出現位置（インデックス）をマップに記録し、その後配列を走査して「現在のインデックス＝最後の出現位置」である要素だけを出力します。

START
Step 1-> 関数 void printelements(int a[], int n) を宣言
    STL の unordered_map<int, int> ele を用意
    ループ For int i=0 and i<n and i++
        ele[a[i]] = i を設定（最後の出現位置を記録）
    ループ For int i=0 and i<n and i++
        IF ele[a[i]] == i
            a[i] を出力
        End
    End
Step 2 -> main()
    配列 a[]={4,2,2,4,1,5,1} を宣言
    int n = sizeof(a)/sizeof(a[0]) を宣言
    関数 printelements(a, n) を呼び出す
STOP

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void printelements(int a[], int n) {
    unordered_map<int, int> ele;
    // 各要素の最後の出現位置を記録
    for (int i = 0; i < n; i++)
        ele[a[i]] = i;
    // 現在の位置が最後の出現位置と一致する要素のみ出力
    for (int i = 0; i < n; i++) {
        if (ele[a[i]] == i)
            cout << a[i] << " ";
    }
}
int main() {
    int a[] = { 4,2,2,4,1,5,1 };
    int n = sizeof(a) / sizeof(a[0]);
    printelements(a, n);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

2 4 5 1

処理のポイント

• 時間計算量： O(n) — 配列を2回走査するだけです。
• 空間計算量： O(n) — 各要素の最後の出現位置を格納するためのマップが必要です。
• unordered_map に同じキーで代入すると値が上書きされるため、ループ終了時には自動的に最後の出現インデックスが残ります。
• 2回目の走査では元の順序のまま比較するため、出力結果も相対的な順序が保たれます。