代码之家 › 专栏 › 技术社区 › CeejeeB

如何比较两组不同匹配的数组

linq algorithm arrays c#

CeejeeB · 技术社区 · 6 年前

我还有x个独立的整数数组:(称这些为数据数组)

我正在寻找一个理想的C语言解决方案,但伪代码就足够了。

一些例子:

给定主数组:

[1],
[2, 3],
[4, 5, 6, 7],
[8]

对于数据数组:

[1],
[2],
[3, 9]

结果应该是2。

数据数组1与主1匹配。
数据数组3与主2匹配(但主2已被使用)。

对于数据数组:

[1],
[2, 8]
[2],
[9]

结果应该是3。

数据数组2与主2&4匹配(应仅计数一次,但以后的条目将决定使用哪一个)。
数据数组3与主2匹配(上面匹配了2,4也是)。
数据数组4不匹配

3 回复 | 直到 6 年前

xanatos 6 年前

看起来很简单:

var masters = new[]
{
    new[] { 1 },
    new[] { 2, 3 },
    new[] { 4, 5, 6, 7 },
    new[] { 8 }
};

var data = new[] 
{
    new[] { 1 },
    new[] { 3, 9 },
    new[] { 2 },
};

// Has masters[i] already been "consumed"?
var used = new bool[masters.Length];

// The found indexes in masters. -1 if not found/already used
var res = new int[data.Length];

for (int i = 0; i < data.Length; i++)
{
    // The default condition is "not found"
    res[i] = -1;

    for (int j = 0; j < masters.Length; j++)
    {
        // If masters[j] already used/consumed, then skip it
        if (used[j])
        {
            continue;
        }

        // We are looking for an intersection between masters[j] and data[i]
        if (masters[j].Intersect(data[i]).Any())
        {
            used[j] = true;
            res[i] = j;
            break;
        }
    }
}

那么你就可以

int count = res.Count(x => x != -1);

O(master.Length * data.Length) 或 O(n^3) 如果我们考虑 data[x].Length .

Dmitry Bychenko 6 年前

图问题 , 最大二部匹配 准确地说。在哪里?

: master 数组
第二部分顶点 data 数组
:如果数据数组与主数组共享至少一个项(交集不为空)

完成这项工作后,你可以像

https://www.geeksforgeeks.org/maximum-bipartite-matching/

https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf

Hamid Mir 6 年前

也许这不是完美的解决方案,但它有效

        int[,] master = new int[4,4];
        master[0,0]=1;
        master[1,0]=2;
        master[1,1]=3;
        master[2,0]=4;
        master[2,1]=5;
        master[2,2]=6;
        master[2,3]=7;
        master[3,0]=8;
        int[,] data = new int[3,2];
        data[0,0]=1;
        data[1,0]=2;
        data[2,0]=3;
        data[2,1]=9;

        bool [] usedmaster= new bool[4];
        for (int i=0;i<4;i++) usedmaster[i]=false;    

        for (int di=0;di<3;di++)
        {
            for (int dj=0;dj<2;dj++)
            {
                if (data[di,dj]>0)
                {
                    int mi=0,mj=0,k=0;
                    foreach (int n in master)
                    {
                        if (data[di,dj]==n)
                        {
                            string ss="";

                                if (usedmaster[k]==true) ss="{but master "+(k).ToString()+ " used}";

                            Console.WriteLine("Data array "+(di).ToString()+" matched with master "+(k).ToString()+ss);
                            usedmaster[k]=true;
                            k+=1;

                            break;
                        }
                        mj +=1;
                        if (master[mi,mj]==0) 
                        {
                            k +=1;
                            mi +=1;
                            mj=0;
                        }
                        if (mj>3) 
                        {
                            mj=0;
                            mi +=1;  
                            k +=1;
                        }
                    }
                }
            }
        }