Алгоритм нахождения младшего неиспользуемого int в NSArray из NSNumbers

Question

Я боролся с этим уже второй день ... У меня есть NSArray of ints, завернутый в NSNumbers.Мне нужно найти самое низкое положительное значение int, которого нет в массиве.

Answer 1

Вот самая «простая» версия, которую я мог придумать (заметьте, простая, не самая эффективная и т. Д.).

Просто зациклите N раз, пока не найдете номер, который не содержится. Если вы не найдете его, значит, он следующий.

Это также предполагает, что 0 считается правильным ответом.

for (int i = 0; i < [numbersArray count]; i++) {
    if (![numbersArray containsObject:[NSNumber numberFromInt:i]]) {
        return i;
    }
}
return [numbersArray count];

Answer 2

Вы можете использовать NSMutableIndexSet как эффективный способ хранения набора целых чисел. Просто итерируйте по массиву, вставляя их в NSMutableIndexSet, и затем, когда вы закончите, вы можете увеличивать набор индексов, пока не найдете дыру. Вот пример:

int lowestPositiveIntNotInArray(NSArray *array) {
    NSMutableIndexSet *set = [NSMutableIndexSet indexSet];
    for (NSNumber *num in array) {
        [set addIndex:[num intValue]];
    }
    // assuming 0 is a valid result here
    NSUInteger seed = [set firstIndex];
    if (seed > 0) {
        return 0;
    }
    NSUInteger next;
    while ((next = [set indexGreaterThanIndex:seed]) != NSNotFound) {
        if (next - seed > 1) {
            // there's a hole here
            break;
        }
        seed = next;
    }
    return seed+1;
}

Answer 3

Попробуйте этот код:

int lowest = 1; // or zero

for (NSNumber *number in array)
{
    lowest = min ([number intValue], lowest)
}

РЕДАКТИРОВАТЬ: Кажется, я неправильно прочитал OP

int lowest = 1; // or zero

NSArray *tempArray = [array sortedArrayUsingSelector:@selector(compare:)];

for (NSNumber *number in tempArray)
{
    if ([number intValue] == lowest)
    {
        lowest = [number intValue] + 1;
    }
}

Answer 4

Я собирался получить исчерпывающий и менее кодовый ответ.Я скомпилировал решение, используя предложения @Richard J.Ross III, @MarkPowell и @Kevin Ballard, спасибо вам, ребята.

Я извлекаю все свои int в NSMutableIndexSet, который имеет удобную функцию - он всегда сортируется, поэтому нам не нужен sortDescriptor.После этого я объявляю минимально допустимое число.Это удобно, так как таким образом я могу исключить 0. Затем я перебираю множество, пока не найду в нем «дыру».Я использую цикл WHILE, для меня это лучшее приближение к здравому смыслу, т. Е. While :) есть число, совпадающее с моим int, поднимите мое int и попробуйте снова.Если больше нет совпадений, новый самый низкий является правильным.

NSMutableIndexSet *mutableSetOfIDs = [[NSMutableIndexSet alloc] init];

    for (Item *item in itemDatabase) 
    {
        NSUInteger x = item.ID;
        [mutableSetOfIDs addIndex:x];
    }


int lowest = 1;

    while ([mutableSetOfIDs containsIndex:lowest]) 
    {
        lowest++;
    }
    return lowest;

Answer 5

Может быть, вы могли бы попробовать что-то подобное? Я положил его в модульный тест. Если вы не знакомы с синтаксисом, просто посмотрите на логику цикла for (NSNumber *num in listOfNumbers).

- (void)testExample {
    // setup
    NSMutableArray *listOfNumbers = [[NSMutableArray alloc]init];
    [listOfNumbers addObject:[[NSNumber alloc]initWithInt:6]];
    [listOfNumbers addObject:[[NSNumber alloc]initWithInt:4]];
    [listOfNumbers addObject:[[NSNumber alloc]initWithInt:12]];
    [listOfNumbers addObject:[[NSNumber alloc]initWithInt:-12]];

    // sort
    [listOfNumbers sortUsingSelector:@selector(compare:)];

    // get the result
    int result = 0;    
    for (NSNumber *num in listOfNumbers) {
        if ([num intValue] > 0 ) {
            result = [num intValue] - 1;
            break;
        }
    }
    STAssertEquals(result, 3, @"Was not 3");
}

Вы могли бы сделать некоторые другие вещи, такие как добавление переменной bool found, чтобы уведомить, что не было найдено положительных чисел. Или вы можете оптимизировать, прочитав последнее значение в массиве - если оно отрицательное, то все значения в массиве отрицательные.

Answer 6

Я бы сделал что-то вроде расстановки чисел в порядке возрастания.Переберите список и остановитесь и первый положительный номер.Если найденное число - 1 все еще является положительным, то оно является наименьшим положительным числом, или само найденное число является наименьшим.

Answer 7

вы можете использовать быстрая сортировка , чтобы отсортировать массив и взять первый (или последний, в зависимости от того, является ли сортировка серповидной или убывающей)

Answer 8

• Сортировать массив
• Пройдите по массиву, пока не найдете пропущенное число.

Есть ли здесь более сложное требование, которое я пропускаю?