1

给定一个对象列表和一个非传递相等函数，当两个对象相等时返回 true，否则返回 false，我需要找到至少两个对象相等的所有最大子列表。例如 -

val list = List(o1, o2, o3, o4, o5)

和，

isEqual(o1, o2) => true
isEqual(o2, o4) => true
isEqual(o3, o5) => true

结果将是：

List(o1, o2, o4)
List(o3, o5)

请注意，isEqual 是不可传递的，即在上述情况下，即使它们属于同一个子列表，它们o1也可能不等于。o4

4

2 回答 2

0

您可以使用不相交集联合算法来查找所有连接的组件。然后打印列表。以下代码的时间复杂度为 O(NlogN)。weighted_union 将联合的时间复杂度降低到 logN。因此，如果我在最坏的情况下执行联合 N 次，则需要 NlogN。

#include <bits/stdc++.h>
using namespace std;

int Arr[100], size[100];

int root (int i)
{
    while(Arr[ i ] != i)
    {
        Arr[ i ] = Arr[ Arr[ i ] ] ; 
        i = Arr[ i ]; 
    }
    return i;
}

void weighted_union(int A,int B)
{
    int root_A = root(A);
    int root_B = root(B);
    if(size[root_A] < size[root_B ])
    {
        Arr[ root_A ] = Arr[root_B];
        size[root_B] += size[root_A];
    }
    else
    {
        Arr[ root_B ] = Arr[root_A];
        size[root_A] += size[root_B];
    }
}

void initialize( int N)
{
    for(int i = 0;i<N;i++)
    {
        Arr[ i ] = i ;
        size[ i ] = 1;
    }
}

int main() {
    // your code goes here
    initialize(6);
    weighted_union(1,2);
    weighted_union(2,4);
    weighted_union(3,5);


    map<int, vector<int> >m;
    for (int i=1;i<=5;i++) {
        if(m.find(Arr[i])!=m.end()){
            vector<int> x = m[Arr[i]];
            x.push_back(i);
            m[Arr[i]] = x;
        } else {
            vector<int> x;
            x.push_back(i);
            m[Arr[i]]=x;
        }
    }

    for (std::map<int,vector<int> >::iterator it=m.begin(); it!=m.end(); ++it) {
        vector<int> x = it->second;
        for(int j=0;j<x.size();++j) {
            cout<<x[j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}

您可以在此处找到解决方案的链接：http: //ideone.com/vsT9Jh

于 2017-08-08T14:56:55.733 回答
0

您的问题等于查找图的所有连接组件的问题。

所以首先要做的是，将您的列表转换为图 G(V, E)，其中 V 代表顶点，E 代表边：

V = list
E = {(o1,o2) for all o1,o2 in list| o1.Equals(o2)}

之后创建一个 DFS 来查找所有组件

WHILE-EXISTS unvisted node in G DO
     component[i] = DFS(G)
END

当然是 Graphs 本身的组件。组件是您要查找的列表，组件中的顶点是列表的元素。

对于您的示例，图表将如下所示

在此处输入图像描述

注意：由于您必须比较每个对象，因此对话将花费 O(n^2)。要找到所有组件将花费您 O(n)。所以这个算法的渐近运行时间为 O(n^2)

回答您问题中的评论

由于您的问题转换为这个图形问题似乎是正确的，我很确定这是不可能的。如果您将其视为图形，则只需检查每个节点是否与其他节点相连。您也不能在找到一个相等的节点后停止，因为您可能会找到另一个相等的节点，并且通过停止，您会拆分连接的组件。

于 2017-08-08T14:39:03.977 回答