1

我想将数组与公共元素合并。我有这样的数组列表：

List<int[]> arrList = new List<int[]>
{
    new int[] { 1, 2 },
    new int[] { 3, 4, 5 },
    new int[] { 2, 7 },
    new int[] { 8, 9 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 9, 13 }
};

我想像这样合并这些数组：

List<int[]> arrList2 = new List<int[]>
{
    new int[] { 1, 2, 7 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 4, 5, 8, 9, 13 } //order of elements doesn't matter
};

怎么做？

4

3 回答 3

3

让每个数字成为标记图中的一个顶点。对于每个数组，连接由给定数组中的数字指向的顶点。例如，给定数组 (1, 5, 3) 创建两条边 (1, 5) 和 (5, 3)。然后在图中找到所有连接的组件（参见：http://en.wikipedia.org/wiki/Connected_component_(graph_theory)）

于 2013-09-22T13:24:22.567 回答
1

使用不相交集森林数据结构。数据结构支持三种操作：

  • MakeSet(item) - 创建一个包含单个项目的新集合
  • Find(item)- 给定一个项目，查找一组。
  • Union(item1, item2)- 给定两个项目，将它们所属的集合连接在一起。

您可以遍历每个数组，并调用Union它的第一个元素以及在它之后找到的每个元素。完成列表中的所有数组后，您将能够通过再次遍历所有数字并调用Find(item)它们来检索各个集合。产生相同集合的数字Find应放入同一数组中。

O(α(n))这种方法以摊销方式完成合并（α增长非常缓慢，因此出于所有实际目的，它可以被认为是一个小常数）。

于 2013-09-22T13:29:02.737 回答
1

我很确定这不是最好和最快的解决方案，但可以。

static List<List<int>> Merge(List<List<int>> source)
{
    var merged = 0;
    do
    {
        merged = 0;
        var results = new List<List<int>>();
        foreach (var l in source)
        {
            var i = results.FirstOrDefault(x => x.Intersect(l).Any());
            if (i != null)
            {
                i.AddRange(l);
                merged++;
            }
            else
            {
                results.Add(l.ToList());
            }
        }

        source = results.Select(x => x.Distinct().ToList()).ToList();
    }
    while (merged > 0);

    return source;
}

我已经使用List<List<int>>而不是List<int[]>获取AddRange可用的方法。

用法：

var results = Merge(arrList.Select(x => x.ToList()).ToList());

// to get List<int[]> instead of List<List<int>>
var array = results.Select(x => x.ToArray()).ToList();
于 2013-09-22T13:31:57.123 回答