配列から最初のユニークな番号を見つける

Question

私はC＃を使ってテストに答えようとしていますが、問題は配列のN個の整数から最初のユニークな番号を見つけることです。配列に一意の番号がない場合は-1を返します。

たとえば、A = {4,5,4,6,5,5,3,8,6}の場合、A = {3,2,3,2,3}ならば3
を返します。 O（N *ログ（ - -1

予想最悪の場合の時間計算、配列Aの各要素の

範囲[0..1,000,000,000]であり、そしてNの範囲は[1..100,000]でありますN））
予想される最悪の場合の空間の複雑さ - 入力記憶域を超えたO（N）

配列変数Aを反復処理するときにList変数を使用して重複する数値を格納する以下のソリューションを記述できます。

1.このソリューションは、上記の複雑さ要件を満たしていますか？
2. LINQを使用せずにC＃でこれを行うより良いアプローチ/アルゴリズムがありますか？

public int solution(int[] A) 
    { 

     if (A.Length == 1) 
     { 
      return A[0]; 
     } 
     else if (A.Length == 2) 
     { 
      if (A[0] == A[1]) 
      { 
       return -1; 
      } 
      else 
      { 
       return A[0]; 
       } 
     } 
     else 
     { 
      List<int> duplicateList = new List<int>(); 

      bool isDuplicate = false; 
      for (int index = 0; index < A.Length - 1; index++) 
      {      
       if (duplicateList.IndexOf(A[index]) == -1) 
       { 
        isDuplicate = false; 
        duplicateList.Add(A[index]); 

        for (int searchIndex = index + 1; searchIndex < A.Length; searchIndex++) 
        { 
         if (A[index] == A[searchIndex]) 
         { 
          isDuplicate = true; 
         } 
         if (isDuplicate) 
         { 
          break; 
         } 

         if (searchIndex == A.Length - 1 && isDuplicate == false) 
         { 
          return A[index]; 
         } 
        } 

       } 
      } 

      if ((duplicateList.IndexOf(A[A.Length - 1])) == -1) 
      { 
       return A[A.Length - 1]; 
      } 
      else return -1; 
     } 
    } 

Answer 1

あなたの答えは簡単、ネストされたループ構造から推測される、またはそれ以上のリスト内のindexOfコールの実装に依存することができるようO(n^2)の時間複雑性を持っています。したがって

あなたは、配列の最初の番号を見つけるために辞書をキーと値のペアとして配列に数字とそれらの発生頻度とそのインデックスを格納してから横断するC＃で辞書インターフェイスを使用することができます O(nlogn)にそれを最適化します頻度は1です。