C++で配列の重複要素を削除し、各要素の右端の出現だけを残すプログラム

問題の概要

n個の要素を含む配列Aがあるとします。この配列から重複する要素を削除し、各要素について配列内で最も右側に出現するものだけを残したいと考えます。その際、残った一意な要素同士の相対的な順序は変更してはいけません。

例えば、入力が A = [1, 5, 5, 1, 6, 1] の場合、出力は [5, 6, 1] となります。各要素の右端の出現だけが残り、元の配列での順序が保たれていることがわかります。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

サイズ1200の2つの配列 b と vis を定義する
x := 0
n := A のサイズ
i := n - 1 から i >= 0 まで、i を 1 ずつ減らしながら繰り返す:
    vis[A[i]] が 0 の場合:
        b[x] := A[i]
        x を 1 増やす
        vis[A[i]] := 1
i := x - 1 から i >= 0 まで、i を 1 ずつ減らしながら繰り返す:
    b[i] を出力する

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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

void solve(vector<int> A) {
    int b[1200], vis[1200], x = 0;
    int n = A.size();
    for (int i = n - 1; i >= 0; i--) {
        if (!vis[A[i]]) {
            b[x] = A[i];
            x++;
            vis[A[i]] = 1;
        }
    }
    for (int i = x - 1; i >= 0; i--)
        cout << b[i] << ", ";
}
int main() {
    vector<int> A = { 1, 5, 5, 1, 6, 1 };
    solve(A);
}

入力

{ 1, 5, 5, 1, 6, 1 }

出力

5, 6, 1,

アルゴリズムの解説

このアルゴリズムのポイントは、配列を右から左へ走査することです。各要素について、補助配列 vis を使ってその値がすでに記録済みかどうかを確認します。まだ記録されていない要素、つまりその値の最も右側の出現だけを結果配列 b に追加していきます。

走査が完了した後、結果配列を逆順に出力することで、元の配列での相対的な順序を保ったまま、一意な要素のリストを得ることができます。

計算量

時間計算量： O(n) — 配列を1回走査するだけなので、要素数に対して線形時間で処理できます。

空間計算量： O(n) — 結果を格納する配列と、出現を追跡する訪問配列が必要です。