CodeSignal - firstDuplicateにチャレンジ #Java

コーディングしなさすぎてコーディングを忘れたエンジニアがコーディングを思い出すためにコーティングします。
今回は、アメリカのコーデイング練習サイトCodeSignalの問題「firstDuplicate」を解いていきます。
サイトによると、この問題はGoogleの面接で出されたようです。

問題

a = [2, 1, 3, 5, 3, 2]

上のような数値の配列が渡されるので、左から見ていって最初に重複した数値を探します。
最初というのは、上の例なら、左から見ていくと3の重複が最初に検知できるので、答えは3です。

たしかに2も重複していて、1個目の2は配列の冒頭で登場しますが、2個目の2が出てくる前に3の重複が見つかるので、答えは2ではありません。

もし配列の中に重複した数値がなければ-1を返します。

制約：
1 ≤ a.length ≤ 10^5
⇨配列の要素数は1以上10,000以下
1 ≤ a[i] ≤ a.length
⇨配列内の数値は1以上、配列の要素数以下
たとえば[2, 2]なら、配列の要素数は2なので、中の数値も2以下（1か2）になります。
[2, 9]や[160, 3]はなしです。

考え方・解説

まず最初に思いつくのは、ブルートフォースです。
ブルートフォースとは、力技で問題を解くことを意味し、単純な考えでいいけど計算量が多くなるのがデメリットです。

a = [2, 1, 3, 5, 3, 2]であれば、まず最初の数値2を基準にし、その後の値1, 3, 5, 3, 2と比較し、重複が見つかればその位置のindexを変数に格納します。
2個目の2はindex5で見つかるので、5を変数に格納します。
次に1を基準にし確認し、重複なし。
3を基準にし、index4の位置で重複が見つかります。そしたら変数の5よりももっと早いindexで重複が見つかったので、変数を4に書き換えます。
同じ要領ですべての値を確認し終えたあと、変数の格納されているindexを使って、a[変数]のようにして、配列から値を取り出せばOKです。

この方法は、普通に答えを目で探すときの方法と同じ要領だと思うので、簡単に思いつくのですが、ベストではありません。
なぜなら、ネステッドループ(ループの中にループがある状態)になるので、計算量が多くなるからです。
そこでなんとかループを一個できないかと考えると、すでに見た数値を別の集合体に突っ込んで、ループで見ていく数値がその集合体の中にあるか確認する方法が思い浮かびます。

もし既に見た（集合体の中にある）のであれば、その値が答えです。
なぜなら既に集合体にある＝今回が2回目の登場なので、その値は重複しており、かつ一番最初に検知した重複になるからです。

Javaで書くとこんな感じです。
集合体は別に順番を持っていなくていいし、重複を許可しない方が無駄が少ないので、HashSetを使用しています。

solution.java

int firstDuplicate(int[] a) {
    HashSet<Integer> seen = new HashSet<>();
    for (int i=0; i<a.length; i++){
        if (seen.contains(a[i])){
            return a[i];
        } else {
            seen.add(a[i]);
        }
    }
    return -1;
}

コードの説明
forで配列の要素を一つづつチェックしています。
もしその要素の文字をHashSetの中で検索し、もし初見であれば、HashSetに突っ込みます。
逆に、すでにHashSetの中に存在している場合はそれが2回目の登場なので答えとして返却します。

学んだこと

要は、ブルートフォースはベストではないので、どうやって別の解き方を考えるかがキーだと思います。
その場合、ネステッドループをなくし、ループを一つにする方法があります。

ループを一つ減らしたいと言うことは、ループで確認する値と突き合わせるのは、過去にループで見た値しかありません。（ループが一個しかないので、ネステッドループのように先の配列の値を検索することはできない）

そのため、過去にループで見た値をどこかに格納しておかなければいけません。そこで集合体を利用します。
とはいえ、過去に見た値をすべて集合体に突っ込んだらそれは結局ネステッドループしてるようなものなので、集合体をもっとスマートにしたいです。
そのため、JavaのHashSetのような重複を許さない集合が利用できます。
集合の要素が少なければ、その分検索も早くなります。