はソートされていないセット<code>A</code><code>x</code>は、いくつかの整数<code>m</code>よりも大きくする必要があることなど<code>A</code>の要素ではない最小の整数<code>x</code>を見つけるための最も効率的なソリューション が何であるかを考えると、アレイ

Question

にない最小の整数を見つけますか？

入力：A = {7, 3, 4, 1}、m = 5出力

：x = 6

私はCでの解決策を探していますが、擬似コードのいずれかの種類が役立つだろう...この問題はOで解決することができる（N）ここで、nは設定されたサイズですか？

Answer 1

私はそれを使って余分な配列を解決しました。ここで 'len'は配列の長さです。

int findMin(int *arr,int n,int len) 
{ 
    int *hash; 
      if(len==0) 
       {return -1; //fail 
       } 
    hash=(int*)calloc(len,sizeof(int)); //hash function I'm using is f(x)=f(x)-n; 
    int i; 
    for(i=0;i<len;i++){ 
     if(arr[i]>n && arr[i]<len+n){ //because max element can't be more than n 
      hash[arr[i]-n]++; 
     } 
    } 

    i=1; 
    while(i<len){ 
     if(hash[i]==0) 
      return len+i; 
     i++; 
    } 
      return len+n+1; 
} 

このソートの順番は、実行時間がO（n）、O（n）である。

Answer 2

次のJavaコードは、あなたのために働く必要があります。

public static int findMinNotInArray(int array[], int n) { 
    int frequency[] = new int[array.length]; 

    if (n < max(array)) { 
     for (int i = 0; i < array.length; i++) { 
      if (array[i] > n && array[i] < n + array.length) 
       frequency[array[i] - (n + 1)]++; 
     } 

     for (int i = 0; i < frequency.length; i++) { 
      if (frequency[i] == 0) 
       return i + n + 1; 
     } 
     return -1; 
    } else { 
     return n + 1; 
    } 
} 

public static int max(int array[]) { 
    int max = array[0]; 
    for (int i = 1; i < array.length; i++) { 
     if (array[i] > max) { 
      max = array[i]; 
     } 
    } 
    return max; 
} 

上記のコードは、単に(n+1) + lengthOfAにn+1から番号を追跡し、この範囲からいずれかの配列に存在するか否か！そして、最初に存在しない数字を返します！

Answer 3

私は考えていますが、最も実現可能なアプローチは配列を最初にソートすることです。次に、mのバイナリ検索を実行して、隣接するものが複数離れている次のポイントを線形検索します。

このアプローチの複雑さはソートアルゴリズムの複雑さです。ほとんどの場合、O（nlogn）です。