[解決済み] 最小のインデックスを持つ配列の中で、最初に重複する要素を見つける。

質問

以下のような重複した要素を含む配列があります。

2番目に出現するインデックスが最小となる、最初の重複した番号を見つける。言い換えれば、重複する数字が1つ以上ある場合、2番目に出現する数字が他の数字の2番目に出現する数字よりも小さいインデックスを持つ数字を返す。そのような要素がない場合は、-1を返す。

a = [2, 1, 3, 5, 3, 2]の場合、出力は次のようになります。 firstDuplicate(a) = 3.

重複しているのは、2番と3番の2つです。2番目に出現する3は2番目に出現する2よりもインデックスが小さいので、答えは3です。

私はこれを試してみました．

int firstDuplicate(int[] a) {
  Set<Integer> set = new HashSet<>();
  Map<Integer, Integer> hm = new HashMap<Integer,Integer>();
  Map.Entry<Integer, Integer> min = null;
  for(int i=0;i<a.length;i++){
       // if(!hm.containsKey(a[i]))
              hm.put(a[i],i);
  }
  for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
        if(min == null || entry.getValue() < min.getValue()){
              min = entry;
        }
  }
  return min == null ? new Integer(-1) : min.getKey();

}

これはうまくいきませんが、ネットで別の解決策を得ました。

int firstDuplicate(int[] a) {
  Set<Integer> set = new HashSet<>();
  Map<Integer, Integer> hm = new HashMap<Integer,Integer>();
  Map.Entry<Integer, Integer> min = null;
  for(int i=0;i<a.length;i++){
        if(set.add(a[i])==false && !hm.containsKey(a[i]))
              hm.put(a[i],i);
  }
  for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
        if(min == null || entry.getValue() < min.getValue()){
              min = entry;
        }
  }
  return min == null ? new Integer(-1) : min.getKey();

}

Hashsetは重複を許さないので、このif条件はどのように機能するのか、どなたか教えてください。

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

最初の試みが失敗した理由は、配列の要素をキーとして Map この場合、すでに存在するかどうかを確認する必要があります。 Map .

あなたが見つけた代替コードは、何か違うことをしています。それは Set で現在の配列要素がすでに出現しているかどうかを調べ、 そうであればそれをキーとして Map は、まだそこにない場合だけです。つまり Map は、配列内で複数回出現する要素のみを含み、各要素に関連付けられたインデックスは、最初の重複の出現箇所となります。つまり、配列 {2, 1, 3, 5, 3, 2} は、その Map を含むことになります。 {2=5, 3=4} . そして、最小の値を持つキー（最初の重複のインデックスに対応する）を返します。

しかし Map は不要です。なぜなら、重複を見つける必要があるのは1つだけで、すべて見つける必要はないからです。そのため Set を使って最初の重複を探し出し、それを返します。

int firstDuplicate(int[] a) 
{
    Set<Integer> set = new HashSet<>();
    for(int i=0;i<a.length;i++){
        if(!set.add(a[i])) {
            return a[i];
        }
    }
    return -1; // no duplicates found 
}

これは set.add() を返す false もし Set は、追加したい要素をすでに含んでいます。一度 false で初めて、最初の重複を発見したことになります。