将数组与公共元素合并

本文关键字：元素 合并 数组 | 更新日期: 2023-09-27 18:32:15

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

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
};

怎么办？

将数组与公共元素合并

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

我很

确定这不是最好和最快的解决方案，但有效。

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();

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

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

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

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

相关文章：