algorithm - 查找行之间矩阵的公共(public)元素

Question

如果有一个 4*2 矩阵:A = [1,2;3,4;5,6;7,1]我需要找到那些行之间至少有一个共同元素的行。例如在上面的例子中，第 1 行和第 4 行有 1 个共同点。这个矩阵行可以很长。最好的算法/逻辑是什么

我尝试了以下算法:

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 列，而且只有 2 列。它有N行

没有成功

Answer 1

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

这分为两部分:

1. 找到一种方法来计算两行是否由边连接，并以此为基础构建图形表示。
2. 找出图中的连通分量。

对于第二部分，有标准算法，如 this Wikipedia article 中所讨论。 .那么让我们转到第一部分。

判断两行是否有共同元素的一种方法是将元素转储到两个集合结构中，并检查两个集合的交集是否为空。许多编程语言都有内置的集合数据结构(通常基于散列)来相当容易地做到这一点(就编程工作量而言)。但是，这不会非常有效，尤其是对于大量行。但是，它可能足以满足您的目的。

如果时间复杂度很重要，我会倾向于尝试一种稍微不同的方法:对每一行进行排序。这会在开始时增加额外的工作量，但当您成对比较所有行时会得到返回。例如，通过比较最小值和最大值，您可以快速检测两行是否具有不相交的值范围(因此不可能有共同的元素)。此外，如果行已排序，您可以(通过一些仔细的簿记)对两行进行耦合线性扫描以在线性时间内搜索公共(public)元素。