Return 所有数字不在任何其他集合中的所有集合

Question

我最近不得不解决以下算法问题，这让我很困惑。

Suppose you have an array of sets that contain integers. Write a function that returns all sets where all of its numbers are not in any other set.

EXAMPLE {0,4,9}, {3,4,5}, {6,7,8}

RESULT {6,7,8}

代码应在 Objective-C 或 Swift 中。

[编辑]

到目前为止我想出了类似的东西，但无法真正完成它。

- (NSArray*) getDisjointedSets:(NSArray*)sets {
    NSArray* resultedSet;
    NSMutableArray* indexDoesntExistInSets = [NSMutableArray array];
    [sets enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSArray* nextIndexArray = [sets objectAtIndex:idx+1];
        NSNumber* numberIndex = obj;
        [nextIndexArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSNumber* numberNextIndex = obj;
            if (numberIndex.intValue == numberNextIndex.intValue) {
               // number exists in the next set, continue

               *stop = YES;;
            } else {
                [indexDoesntExistInSets addObject:numberIndex];
            }
        }];
    }];
    return resultedSet;
}

Answer 1

您的代码迭代数组的数组。但是你得到下一个数组，迭代它的数字，但尝试将每个数字与当前集合进行比较。

假设您有 NSArray 个 NSArray 个对象，您可以这样做：

- (NSArray *)getDisjointedSets:(NSArray *)sets {
    NSMutableArray *resultSet = [NSMutableArray array];
    for (NSArray *arrayA in sets) {
        BOOL noMatch = YES;
        for (NSArray *arrayB in sets) {
            // Skip if both are the same array
            if (arrayA != arrayB) {
                NSMutableSet *setA = [NSMutableSet setWithArray:arrayA];
                NSSet *setB = [NSSet setWithArray:arrayB];
                [setA intersectSet:setB];
                if (setA.count) {
                    // The two sets have something in common
                    noMatch = NO;
                    break;
                }
            }
        }

        if (noMatch) {
            [resultSet addObject:arrayA];
        }
    }

    return resultSet;
}

测试代码：

NSArray *sets = @[
    @[ @0, @4, @9 ],
    @[ @3, @4, @5 ],
    @[ @6, @7, @8 ]
];
NSArray *result = [self getDisjointedSets:sets];
NSLog(@"results = %@", result);

Return 所有数字不在任何其他集合中的所有集合

Return all sets where all of its numbers are not in any other set

algorithm

objective-c

set