在NSNumbers的NSArray中查找最低未使用int的算法

Question

我纠结了第二天。。。我有一个整数的NSArray，包装成NSNumbers。我需要找到数组中不存在的最低正整数。

Answer 1

您可以使用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 2

这是我能想到的"最简单"的版本（注意，简单，不是最高效的，等等）。

简单地说，循环N次，直到找到一个不包含的数字。如果你找不到，那一定是下一个。

这也是假设0被认为是一个有效的答案。

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

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

• 对数组进行排序
• 遍历数组，直到找到一个丢失的数字

这里有没有我遗漏的更复杂的要求？

Answer 5

您可以使用quicksort对数组进行排序，并获取第一个（或最后一个，这取决于排序是新月形还是递减）

Answer 6

我会做一些事情，比如按递增顺序排列数字。在列表上迭代，并停止和第一个正数。如果找到的数字-1仍然为正，则它是最小的正整数，或者发现的数字本身是最小的。

Answer 7

也许你可以试试这样的东西？我把它放在单元测试中。如果您不熟悉语法，只需查看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 8

我想要一个全面的、更少代码的答案。我使用@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;