查找行之間矩陣的公共元素

如果存在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

查找行之間矩陣的公共元素

回答

相關問題