[解決済み] アルゴリズム：配列から重複する整数を削除する効率的な方法

質問

この問題は、マイクロソフトのインタビューから得たものです。

ランダムな整数の配列が与えられる。 C言語でアルゴリズムを書きなさい。 重複した数字を取り除き、元の配列の一意な数字を返すアルゴリズムを を返すアルゴリズムをCで書きなさい。

例 入力 {4, 8, 4, 1, 1, 2, 9} 出力 {4, 8, 1, 2, 9, ?, ?}

1つの注意点は、期待されるアルゴリズムは配列を最初にソートすることを要求してはいけないということです。また、ある要素が削除された場合、後続の要素も同様に前方にシフトされなければなりません。いずれにせよ、要素が前方にシフトされた配列の末尾にある要素の値は無視できます。

更新しました。 結果は元の配列で返さなければならず、ヘルパーデータ構造（例えばハッシュテーブル）は使ってはいけない。ただし、順序の保持は必要ないかと思います。

更新2です。 なぜこのような非現実的な制約があるのかと思われるかもしれませんが、これはインタビューでの質問で、これらの制約はすべて、私がどのように違うアイデアを思いつくか、考える過程で議論されるものなのです。

どのように解決するのか？

どうでしょう。

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

O(n^2)以下であることが望ましい。