一貫性のために一連の数値を調べる

Question

私は整数の配列を維持しています。この配列の整数は常に0から順になることが重要です。たとえば、配列に5つの整数がある場合、その値は0,1,2,3,4（いずれの順序であっても）でなければなりません。

これを確認する簡単で効率的な方法を設計したいと思います。配列に0からarray.count - 1の順番ですべての正の整数が含まれている場合は、trueを返します。

これを処理するためのいくつかの異なるアイデアをお聞きしたいと思います。

- (BOOL)itemsSequencedCorrectlyInSet:(NSSet *)testSet{ 
     for (NSInteger i = 0; i < testSet.count; i++) { 
       if (![testSet containsObject:[NSNumber numberWithInteger:i]]) { 
        return NO; 
       } 
     } 

     return YES; 
    } 

Answer 1

これはあなたのitemsSequencedCorrectlyInSetからあまり違いはありません：メソッドではなく、[NSSet containsObject：]を実行するよりも速い可変インデックスセットを使用します。あなたが何千ものテーブル行を取得するまで、おそらく問題はありません。とにかく、ここでの重要な洞察は、ピジョンホールの原理は、N以下の整数がN未満であり、重複がない場合、0 ... N-1のそれぞれを1回だけ持つと言います。

-(BOOL)listIsValid:(NSArray*)list 
{ 
    NSMutableIndexSet* seen = [NSMutableIndexSet indexSet]; 

    for (NSNumber* number in list) 
    { 
     NSUInteger n = [number unsignedIntegerValue]; 

     if (n >= [array count] || [seen containsIndex:n]) 
      return NO; 

     [seen addIndex:n]; 
    } 

    return YES; 
} 

Answer 2

ここに私の現在の実装では、（TESTSETはNSNumbersのセットです）です。これは、N個の整数の他の集合が持つプロパティではありません。

私はこれを代替案として提供していますが、これは適合性、性能、効率性についての主張をしていません。Nが大きくなるにつれて問題が生じることを認識しています。

Answer 3

それとも、あなたは順番に各のパワーに2を上げると、整数[0..N-1]与えられた合計は-1+2^Nになります -

Answer 4

基本的には、配列が[0...n-1]の順列であるかどうかがテストされます。これには時間とメモリの両方でO(n)という簡単なアルゴリズムがあります。たとえば、PDF fileを参照してください。

ときどきO(n)の時間とメモリにO(1)という非常に単純なチェックを使用します。それは理論上は誤検知を返すことがありますが、ほとんどの間違いを見つけるには良い方法です。これは、次の事実に基づいています。

0 + 1 + 2 + ... + n-1 == n * (n-1)/2 
0 + 1² + 2² + ... + (n-1)² == n * (n-1) * (2 * n - 1)/6 

私はObjective-Cのを知りませんが、コードはC＃で次のようになります。

bool IsPermutation(int[] array) 
{ 
    long length = array.Length; 
    long total1 = 0; 
    long total2 = 0; 

    for (int i = 0; i<length; i++) 
    { 
     total1 += array[i]; 
     total2 += (long)array[i] * array[i]; 
    } 

    return 
     2 * total1 == length * (length - 1) && 
     6 * total2 == length * (length - 1) * (2 * length - 1); 
}