如果包含匹配對象，則要組合數組的數組

我有使用僞代碼解釋我正在嘗試做什麼的對象列表（列表可能是一個集合，可變數組等等）...如果包含匹配對象，則要組合數組的數組

@[ @[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'）。

我以這樣一種方式提出這個問題，希望能夠爲建議的解決方案開闢更廣闊的空間，因爲有人可能會知道一種我沒有遇到的技術。

來源

2013-10-01 Ian Clay

你是什麼意思「數字可能是NSObjects」 - 你只能在NSArray或任何其他Objective-C集合類中存儲對象。 – trojanfoe

我已經更新了這個問題。它更清楚嗎？ –

你期望有多少個對象和多少個數組？至少有兩種方法可以做到這一點 - 簡單但緩慢，速度極快但有點複雜。選擇取決於問題的大小。 – dasblinkenlight

您可以採取兩種方法 - 一種簡單直接的方法，適用於少量對象，或者即使對於極大型對象也能正常工作的高級方法。

第一種方法使用一個簡單的算法，該算法從您的初始數組開始，將其內部數組複製到NSSet s中，並檢查每對公用項的存在情況。你可以用intersectsSet:方法來完成。如果一對組具有相同的元素，則將其替換爲這些組的集合。爲此，使用setByAddingObjectsFromSet:。每次合併兩個集合時，設置一個特殊標誌，表示集合集合已被修改。如果在檢查所有對集合時發現該標誌已設置，則用已修改集合替換之前的集合數組，並從頭開始進行成對檢查。由於每個設置標誌的步驟都會減少至少一個設置的數量，因此該循環將保證完成。一旦循環完成，將一組數組轉換爲數組數組。

第二種方法更復雜，但速度也更快。構建一個disjoint-set data structure，向其中添加每個數組的元素，然後再次遍歷原始數組，檢查每個元素已結束的集合。當兩個元素在同一個集合中時，將它們放入同一個數組中。

來源

2013-10-01 13:20:04 dasblinkenlight

不相交的好主意。更確切地說，你需要迭代數組，然後每個數組將所有對象添加到不相交集結構中，並將每個元素的「聯合」（「合併」，「連接」，「連接」，無論您稱爲操作）與它的數組的第一個元素（從而合併所有數組的元素）。所有這些都可以在幾乎線性的時間完成。 –

@VadimYelagin正確，該操作的正式名稱是「union」。我需要一次實現這個數據結構，並沒有那麼糟糕，而且它的運行速度非常快。 – dasblinkenlight

是的，我很喜歡在幾年前實施它。很少的代碼，雖然「逆阿克曼函數分攤時間每個操作」聽起來屁股:-) –

就算法而言，您需要的是找到一個bipartite graph的connected components（算法可以通過下面的鏈接找到），其中一組頂點用於數組，另一組頂點用於數字，邊連接每個陣列都有其每個元素。

然後爲每個組件創建一組由所有與第二組頂點對應的數字組成的數字。

可能沒有保留輸入數組元素排序的概念。

來源

2013-10-01 13:07:13

這個算法做你想要的。但它可能不是最佳的優化方式。

-(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-01 13:20:29

謝謝解析器，我認爲這解決了我的問題，很多要通過您的代碼學習。謝謝。 –

@IanClay如果您有任何理解代碼的疑問，您可以問我。 –

更不用說可怕的無效了，可能存在一個錯誤：在刪除第k個元素後，應該減少'k'。因爲在將第（k + 1）個元素刪除併成爲第k個元素之後，k將會增加，並且元素將被跳過。另外，它應該是'removeObjectAtIndex：'，因爲可能有重複的元素。 –

一個更清潔的方法是使用集合，並簡單地測試集合是否相交。參見[NSSet intersectsSet]。

來源

2013-10-02 04:05:21 pickwick

這是我使用@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-19 10:37:42

如果包含匹配對象，則要組合數組的數組

回答

相關問題