ios - 如果包含匹配对象，则要合并的数组的数组

Question

我有对象列表(列表可以是一个集合，一个可变数组等)，使用伪代码来解释我正在尝试执行的操作...

 @[ @[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”)。

我问这个问题的方式希望为建议的解决方案开辟更大的范围，因为有人可能知道一种我从未遇到过的解决方法。

Answer 1

您可以采用两种方法-一种简单明了的方法对少量对象适用，或者一种高级方法即使对大量对象也适用。

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

第二种方法更复杂，但是也更快。构造一个disjoint-set data structure，向其中添加每个数组的元素，然后再次遍历原始数组，检查其每个元素结束的集合。当两个元素在同一集合中时，将它们放入同一数组中。