1

我有对象列表（该列表可以是一个集合、一个可变数组等），使用伪代码来解释我想要做什么......

 @[ @[1, 2, 3], @[2, 5, 6], @[8, 9] ]; // the numbers are NSObjects, using numbers here for simplicity.

如何组合包含 1 个或多个匹配项目的项目：

@[ @[1, 2, 3, 5, 6], @[8, 9] ];

（1、2、3 与 5、6 组合在一起，因为它们都包含“2”）。

我以一种希望为建议的解决方案开辟更广阔范围的方式提出这个问题，因为有人可能知道一种我没有遇到过的技术来做到这一点。

4

5 回答 5

3

您可以采用两种方法 - 一种简单直接的方法适用于少量对象，另一种高级方法即使适用于非常大的对象集也能正常工作。

第一种方法使用一个简单的算法，从您的初始数组开始，将其内部数组复制到NSSets 中，并检查每对集合是否存在共同项目。你可以用这个intersectsSet:方法来做。如果一对集合具有共同元素，则将其替换为集合的并集。为此使用setByAddingObjectsFromSet:。每次合并两个集合时，设置一个特殊标志，表示集合的集合已被修改。如果在检查所有成对的集合时，您看到设置了此标志，请将先前的集合数组替换为修改后的集合，然后从头开始成对检查。由于设置标志的每一步都会将集合的数量至少减少一个，因此可以保证此循环完成。循环完成后，将集合数组转换为数组数组。

第二种方法更复杂，但也更快。构造一个不相交集数据结构，将每个数组的元素添加到其中，然后再次遍历原始数组，检查每个元素已结束的集合。当两个元素在同一个集合中时，将它们放入同一个数组中。

于 2013-10-01T13:20:04.327 回答
1

这个算法做你想做的事。但它可能不是最好的优化方式。

-(void)doSomeWork{
    NSMutableArray *arr =  [@[ @[@1, @2, @3], @[@4, @5, @6], @[@8, @9]] mutableCopy];
    NSLog(@"abc = %@",arr);
    for(int i=0; i<arr.count;i++){
        NSArray *subArray = [arr objectAtIndex:i];
        for(int j=0; j<subArray.count;j++){
            for(int k=0; k<arr.count;k++)
                if(i==k){
                    continue;
                }
                else{
                    if([[arr objectAtIndex:k]containsObject:[subArray objectAtIndex:j]]){
                        [arr replaceObjectAtIndex:i withObject:[self addCommonObjectsFrom:[arr objectAtIndex:i] arr2:[arr objectAtIndex:k]]];
                        [arr removeObject:[arr objectAtIndex:k]];

                    }
                }
        }
    }
    NSLog(@"abc = %@",arr);
}

-(NSArray*)addCommonObjectsFrom:(NSArray*)arr1 arr2:(NSArray*)arr2{
    NSMutableSet *set1 = [[NSMutableSet alloc]initWithArray:arr1];
    [set1 addObjectsFromArray:arr2];
    return [set1 allObjects];
}
于 2013-10-01T13:20:29.107 回答
0

就算法而言，您需要找到二分图的连通分量（通过链接找到的算法），其中一组顶点用于您的数组，另一组顶点用于您的数字，边连接每个数组与它的每一个元素。

然后为每个组件创建一组数字，其中包含对应于第二组顶点的所有数字。

可能没有保留输入数组中元素顺序的概念。

于 2013-10-01T13:07:13.237 回答
0

一个更清洁的方法是使用集合，并简单地测试集合是否相交。请参阅 [NSSet 相交集]。

于 2013-10-02T04:05:21.093 回答
0

这是我使用@dasblinkenlight 技巧的变体编写的代码。

  NSMutableArray *compareSets = [NSMutableArray new];
  NSMutableArray *t =   [@[ @[@1, @2, @3],@[@12,@13,@14,@15,@16], @[@2, @5, @6], @[ @8, @9], @[@10, @2, @9], @[@11,@12222], @[@123, @34, @342, @1000], @[@34, @10001]  ] mutableCopy] ;
   for (NSArray *m in t) {
    NSMutableSet *b = [[NSMutableSet alloc] initWithArray:m];
    [compareSets addObject:b];
   }

 int reRunSet = 0;
 int runStore = 0;
 while (true) {
    int setCount = compareSets.count;

    if (setCount == 1) {
        break;
    }

    runStore = (int) setCount;
    for (int i = (runStore - 1); i > 0; i--) {
         if ( [compareSets[0] intersectsSet:compareSets[i]] ) {
            setCount++;
            [compareSets[i] unionSet:compareSets[0]];

            [compareSets removeObjectAtIndex:0];

        }
    }

    NSMutableSet *t = [[NSMutableSet alloc] init];
    [t setSet:compareSets[0]];

    [compareSets removeObjectAtIndex:0];
    [compareSets addObject:t];
    if (runStore != setCount) {
        reRunSet = 0;
        continue;
    }

    if (setCount == compareSets.count) {
        reRunSet ++;
        if (reRunSet == setCount) {
            break;
        }
    }
}
NSLog(@"compared sets finish = %@", compareSets);
于 2013-10-19T10:37:42.653 回答