Проверка последовательности чисел на согласованность

Question

Я поддерживаю массив целых чисел. Важно, чтобы целые числа в этом массиве всегда были в последовательности от 0. Например, если в массиве 5 целых чисел, их значения должны быть 0, 1, 2, 3, 4 (хотя и в любом порядке).

Я хотел бы разработать простой, эффективный метод, который проверяет это. Он вернет true, если массив содержит все натуральные числа в последовательности от 0 до array.count - 1.

Мне бы очень хотелось услышать несколько разных идей для этого!

Answer 1

Или, учитывая целые числа [0..N-1], если вы повысите 2 до степени каждого по очереди, сумма будет -1+2^N. Это не свойство, которое имеет любой другой набор из N целых чисел.

Я предлагаю это в качестве альтернативы, не заявляя о пригодности, производительности или эффективности, и я признаю, что будут проблемы, когда N станет большим.

Answer 2

В основном вы хотите проверить, является ли ваш массив перестановкой [0...n-1].Есть простые алгоритмы для этого, которые O(n) как по времени, так и по памяти.См., Например, этот файл PDF .

Иногда я использую очень простую проверку, которая 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

Я не знаю цель-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);
}

Answer 3

Это не слишком отличается от вашего 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;
}

Answer 4

Вот моя текущая реализация (testSet - это набор NSNumbers) -

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

         return YES;
    }