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 は、両方とも「2」を含むため、5、6 と結合されます)。

私が遭遇したことのないこれを行うための手法を誰かが知っているかもしれないので、提案された解決策のより広い範囲を開くことを願ってこの質問をしています。

4

5 に答える 5

3

使用できるアプローチは 2 つあります。オブジェクトの数が少ない場合に問題なく機能するシンプルで簡単な方法と、非常に大きなオブジェクトのセットでも問題なく機能する高度な方法です。

最初のアプローチは、初期配列から開始し、その内部配列をNSSets にコピーし、共通項目の存在についてセットの各ペアを調べる単純なアルゴリズムを使用します。メソッドでできますintersectsSet:。セットのペアに共通の要素がある場合は、セットの和集合に置き換えます。そのために使用setByAddingObjectsFromSet:します。2 つのセットがマージされるたびに、セットのコレクションが変更されたことを示す特別なフラグを設定します。セットのすべてのペアを調べたときに、このフラグが設定されていることがわかった場合は、以前のセットの配列を変更された配列に置き換えて、ペアごとのチェックを最初から開始します。フラグを設定する各ステップは、少なくとも 1 つのセットの数を減らすため、このループは終了することが保証されます。ループが終了したら、セットの配列を配列の配列に変換します。

2 番目の方法はより複雑ですが、はるかに高速です。互いに素な集合データ構造を構築し、各配列の要素をそれに追加してから、元の配列をもう一度調べて、各要素が最終的に含まれる集合を調べます。2 つの要素が同じセットにある場合は、それらを同じ配列に入れます。

于 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

アルゴリズムに関して必要なのは、配列の頂点のセットと数値の頂点の別のセットを持つ二部グラフの接続されたコンポーネント(リンクをたどることで見つかるアルゴリズム) を見つけることです。エッジは各配列を接続します。その要素のそれぞれで。

次に、コンポーネントごとに、頂点の 2 番目のセットに対応するすべての数値からなる数値のセットを作成します。

おそらく、入力配列からの要素の順序を維持するという考えはあり得ません。

于 2013-10-01T13:07:13.237 に答える
0

はるかにクリーンなアプローチは、セットを使用し、セットが交差するかどうかを単純にテストすることです。[NSSet intersectsSet] を参照してください。

于 2013-10-02T04:05:21.093 に答える