Überprüfen einer Reihe von Zahlen auf Konsistenz

Question

Ich pflege ein Array von ganzen Zahlen. Es ist wichtig, dass zu jeder Zeit die Ganzzahlen in diesem Array in der Reihenfolge von 0 sind. Zum Beispiel, wenn es 5 ganze Zahlen im Array gibt, müssen ihre Werte 0, 1, 2, 3, 4 sein (obwohl in beliebiger Reihenfolge).

Ich möchte eine einfache, effiziente Methode entwerfen, die dies überprüft. Es gibt true zurück, wenn das Array alle positiven ganzen Zahlen in Folge enthält 0 bis array.count - 1.

Ich würde gerne ein paar andere Ideen für den Umgang mit dieser hören!

Answer 1

Dies ist nicht allzu verschieden von Ihrem itemsSequencedCorrectlyInSet : method, aber es verwendet eine veränderbare Indexmenge, die schneller ist als - [NSSet enthältObjekt:]. Wahrscheinlich kein Problem, bis Sie Tausende von Tabellenzeilen haben. Wie auch immer, die wichtigste Erkenntnis hier ist, dass das Pigeonhole-Prinzip sagt, wenn man N ganze Zahlen kleiner als N hat und keiner dupliziert ist, dann hat jeder von 0 ... N-1 genau einmal.

-(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

Hier ist meine aktuelle Implementierung (testSet ist ein Satz von NSNumbers) -

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

     return YES; 
    } 

Answer 3

Oder, da die ganzen Zahlen [0..N-1], wenn Sie 2 auf die Leistung jedes wiederum erhöhen die Summe -1+2^N sein wird. Dies ist keine Eigenschaft, die eine andere Menge von N ganzen Zahlen hat.

biete ich dies als eine Alternative, keinen Anspruch über Eignung, Leistung oder Effizienz zu machen, und ich erkenne, dass es Probleme geben wird, wie N groß wird.

Answer 4

Im Grunde, was Sie testen möchten, ist, wenn Ihr Array eine Permutation von [0...n-1] ist. Es gibt einfache Algorithmen dafür, die O(n) in Zeit und Gedächtnis sind. Siehe zum Beispiel dieses PDF file.

Manchmal verwende ich eine sehr einfache Überprüfung, die O(n) in der Zeit und O(1) im Speicher ist. Es kann theoretisch falsche Positive zurückgeben, aber es ist ein guter Weg, die meisten Fehler zu finden. Es basiert auf den folgenden Tatsachen:

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

ich nicht Objective-C nicht kennen, aber der Code wie folgt in C# aussehen:

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); 
}