CodeFights - FirstDuplicateメソッドの書き込み時の制限時間の問題

Question

私はCodeFightsから以下の問題を解決しようとしています。私は質問の後にJavaで私の答えを残しました。このコードは、最後のものを除くすべての問題に適用されます。時間制限の例外が報告されます。 3000ms（CodeFightの要件）を下回るようにするために私は何ができますか？

注：実際のインタビュー中に実行するように求められているので、O（n）時間の複雑さとO（1）の追加の複雑さのソリューションを作成します。

1からa.lengthの範囲の数字だけを含む配列aが与えられた場合、2番目のオカレンスが最小インデックスを持つ最初の重複番号を見つけます。つまり、重複した数字が2つ以上ある場合は、2番目のオカレンスが2番目のオカレンスよりも小さいインデックス番号を返します。そのような要素がない場合は、-1を返します。

例

= [2、3、3、1、5、2]、出力があるべき firstDuplicate（A）= 3

2つの重複があります番号2及び3の2回目の出現は、2回目の2回目の出現よりも小さい指標であるため、答えは3です。

a = [2,4,3,5,1]の場合、出力は firstDuplicate （a）= -1となる。

入力/出力

[期限] 3000ms

保証制約array.integer（ジャワ） [入力]： 1≤a.length、105≤1≤ [I] ≤a.length。

[出力]複数回アレイで発生し、その第二の発生の最小インデックスを持つ整数

素子。そのような要素がない場合は、-1を返します。

int storedLeastValue = -1; 
    int indexDistances = Integer.MAX_VALUE; 
    int indexPosition = Integer.MAX_VALUE; 

    for (int i = 0; i < a.length; i++) 
    { 
      int tempValue = a[i]; 

      for (int j = i+1; j < a.length; j++) { 
       if(tempValue == a[j]) 
       { 
        if(Math.abs(i-j) < indexDistances && 
         j < indexPosition) 
        { 
         storedLeastValue = tempValue; 
         indexDistances = Math.abs(i-j); 
         indexPosition = j; 
         break; 
        } 
       } 
      } 
     } 

     return storedLeastValue; 

Answer 1

これについて何：

 public static void main(String args[]) { 

      int [] a = new int[] {2, 3, 3, 1, 5, 2}; 
      // Each element of cntarray will hold the number of occurrences of each potential number in the input (cntarray[n] = occurrences of n) 
      // Default initialization to zero's 
      int [] cntarray = new int[a.length + 1]; // need +1 in order to prevent index out of bounds errors, cntarray[0] is just an empty element 

      int min = -1; 
      for (int i=0;i < a.length ;i++) { 
       if (cntarray[a[i]] == 0) { 
        cntarray[a[i]]++; 
       } else { 
        min = a[i]; 
        // no need to go further 
        break; 
       } 
      } 
      System.out.println(min); 
     } 

Answer 2

ソリューションが有する問題は、明示的にO（N）を求めながら（N^2）Oを意味ループの入れ子になった2。また、スペースの制限があるため、追加のSetを使用することもできません（これも簡単な解決法を提供します）。

この質問は、強力なアルゴリズム/グラフ理論の背景を持つ人々には適しています。ソリューションは洗練されており、有向グラフでサイクルのエントリポイントを見つけることが含まれます。あなたがこれらの用語に精通していない場合、私はそれを残して他の質問に移動することをお勧めします。

Answer 3

この演習のための良い答えがここにあります - https://forum.thecoders.org/t/an-interesting-coding-problem-in-codefights/163 - すべてがその場で行われ、それはO（1）ソリューションを提供しています。