objective-c - 检查一系列数字的一致性

Question

我维护一个整数数组。重要的是，此数组中的整数始终从0开始按顺序排列。例如，如果数组中有5个整数，则它们的值必须为0、1、2、3、4(尽管可以按任意顺序)。

我想设计一种简单，有效的方法对此进行检查。如果数组包含从0到array.count-1的所有正整数，则它将返回true。

我很想听听一些不同的想法来处理这个问题!

Answer 1

这与您的itemsSequencedCorrectlyInSet:方法没有太大不同，但是它使用可变的索引集，该索引集比执行-[NSSet containsObject:]的速度更快。在拥有成千上万个表行之前，可能不是问题。无论如何，这里的关键见解是Pigeonhole原理说，如果您有N个小于N的整数并且没有重复的整数，那么您每个0 ... N-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;
}