查找行之间矩阵的公共元素

如果存在4 * 2矩阵： A = [1,2; 3,4; 5,6; 7,1] 我需要查找至少包含行这些行之间通用的元素。例如在上面的例子中，1和4行共有1个。这矩阵行可以是很大的长度。有什么可以成为最好的算法/逻辑，它查找行之间矩阵的公共元素

我尝试下面的算法：对我来说，矩阵只有2列

for(i=0;i<N;i++){ 
    for(j=i+1;j<N;j++){ 
     if(ipArr[i][0] == ipArr[j][0] || ipArr[i][0] == ipArr[j][1] || 
      ipArr[i][1] == ipArr[j][0] || ipArr[i][1] == ipArr[j][1]){ 
       //code to perform for repeating row, having atleast 1 common element. 
     } 
    } 
}

，它只会是2。它是N行

它没有工作

来源

2017-02-17 ShyamSundar R

您是指所有具有共同元素的行对？或者你想要一对单行吗？还是你想要更大的行组共享一个共同的元素？（这些问题都不是很容易，但最后一个更难，我想 - 也需要进一步的定义。）另外，您是什么意思的“最好”？时间表现？内存使用？还有别的吗？ –

它主要是一个算法来分类和查找多少组的行具有共同的元素，一个组可以有> = 2行，我需要找到每个行是每个组的一部分。更多细节越好。如果1,2,3行具有共同元素，则1,2,3一起组成一个组 –

该问题缺乏某些定义。假设你有行（1，2，3），（2,5,6），（3,5,7）。每一行都有一个与其他两个元素相同的元素，但没有元素对于所有三个元素都是共同的。应该如何分组？如果第三行是（4,5,7），那么它不再有与（1,2,3）相同的元素呢？ –

我没有详细的算法为你，但我会处理这为图形算法问题。将每一行看作图的一个顶点。如果两行至少有一个共同的元素，则在顶点之间存在一条边。然后，如果我正确理解您的问题，您正在尝试查找图形的连接组件。（图的连通分量是具有子图中所有顶点通过路径相互连接并且不与超图的任何其他顶点连接的属性的子图。）

这分成两部分部分：

找到一种方法来计算是否两行是通过一个边缘接合，并建立基于该图形表示。
查找图形的连接组件。

对于第二部分，存在标准算法，如在this Wikipedia article中讨论的。那么我们来看第一部分。

确定两行是否具有共同元素的一种方法是将元素转储到两个集合结构中，并检查这两个集合的交集是否为空。许多编程语言都有内置的集合数据结构（通常基于散列）来合理轻松地完成此操作（就编程工作而言）。但是，这不会非常有效，特别是对于大量的行。但是，对于你的目的来说它可能已经足够了。

如果时间复杂性很重要，我会倾向于尝试一种稍微不同的方法：对每一行进行排序。这在开始时会创建额外的工作，但在您将所有行进行两两比较时会有所帮助。例如，通过比较最小值和最大值，可以快速检测两行是否具有不相交的值范围（因此不可能有共同的元素）。另外，如果行被排序，您可以（通过一些谨慎的簿记）对两行进行耦合线性扫描，以线性时间搜索公共元素。

来源

2017-02-17 08:43:16

此解决方案假定您的主要目的是为了找人之间的相似性，你在评论

让每个人（数）是一个节点和行曾提到是边缘与体重1

现在用这个建立一个无向图。

让每个节点也存储它与其他每个节点的“相似性”。这可以通过从该节点到每个其他节点的最短路径找到。（每个节点需要O（n）空间）

将Floyd Warshall算法用于从一个节点到其他每个节点的最短路径。

如果最短路径是天道酬勤这意味着没有相似性和最小的最短路径的最大相似性

时间复杂度：O（N^3），其中n是人/数字的数量

空间复杂度：O（n^2）

来源

2017-02-17 09:54:29

查找行之间矩阵的公共元素

回答

相关问题