查找3個二維數組中的相似行

Question

在Java中解決以下問題的最佳方法是什麼？ 。它有相等數量的行和列的3二維數組：

Array1: 
[1]: {1, 2, 3} 
[2]: {2, 2, 4} 
[3]: {1, 1, 1} 

Array2: 
[1]: {1, 2, 0} 
[2]: {1, 2, 3} 
[3]: {1, 0, 1} 

Array3: 
[1]: {1, 1, 1} 
[2]: {1, 2, 3} 
[3]: {1, 0, 1} 

我需要找出行中存在的所有的數組索引。在上述例子中，答案應該是：[1]，[2]，[2]

數組1 [1]：{1，2，3}

ARRAY2： [ 2]：{1，2，3}

ARRAY3： [2]：{1，2，3}

UPDATE：是否有任何內置函數來做到這一點？或者FOR循環是唯一的解決方案？

Answer 1

我會做到以下幾點：

• 創建一個類，它在陣列中的一行，並實現hashcode和equals。
• 插入每一行中的第一個的兩個陣列（包裹在上面的類）劃分爲兩個HashMaps
• 最後陣列中的每一行中，確定它們是否在HashMaps

編輯＃2存在，實現了該映射需要顛倒。所有的

private Map<MyClass, Integer> map(int[] array){ 
    Map<MyClass, Integer> arrayMap = new HashMap<>(); 
    for (int i; i<array.length; i++) 
     arrayMap.put(new MyClass(array[i]), i); 
} 

private mySearch(){ 
    int[] array1, array2, array3; 

    Map<MyClass, Integer> map1 = map(array1); 
    Map<MyClass, Integer> map2 = map(array2); 

    for (int i=0; i<array3.lenght; i++){ 
     MyClass row = new MyClass(array3[i]); 
     Integer array1Row = map1.get(row); 
     Integer array2Row = map2.get(row); 

     if (array1Row != null && array2Row != null){ 
     // Matching rows found 
     } 
    } 
} 

Answer 2

檢查Arrays.deepEquals()方法。它會檢查兩個數組是否相等。

Answer 3

首先，編寫一個名爲AreRowsEqual()功能，它比較兩個行。所以，現在，問題已被重新編爲Find similar elements in 3 arrays。其次，試着想出一個解決方案，該解決方案與已知知識基於先前知識最接近：在兩個數組中找到相同的元素，則需要一個雙重嵌套for循環。所以，要在三個數組中找到相同的元素，您需要一個三重嵌套循環，對吧？

好吧，現在把它作爲一個壞的，壞的，壞的解決方案來處理，因爲它的時間複雜度是O（n^3）。我們應該能夠做得更好。

考慮一下：爲了讓一個元素在所有3個數組中相似，首先它必須在前兩個中相似;那麼，在接下來的兩個之間必須是相似的。這種算法的複雜性類似於O（x * n），其中x是陣列的數量。好多了，對吧？ （我無法弄清楚O（）會是什麼，幫助任何人？）編輯：事實證明它是O（（n^2）*（x-1）），這比O（ n^3）當n> x - END編輯順便說一下，您可以忘記嚴格要求3陣列，並且只考慮一些x陣列。

我寫了一個方法，收到一個upvote，然後我意識到它不會工作，我刪除它。這是另一個嘗試，我相信會起作用：

創建一個整數的二維數組。我們將稱之爲「矩陣」。該矩陣將有x列，並且行數將是第一個數組的行數。 （是的，即使你的數組​​有不同的長度，這也是可行的。）這個矩陣的單元格中的數字將匹配行索引。因此，例如，在算法描述完成後，矩陣中的一行{ 1, 3, 2 }將告訴我們第一個數組的第1行與第二個數組的第3行和第三個數組的第2行相匹配。我們將使用-1來表示'不匹配'。

因此，矩陣的第一列需要用第一個數組的所有行的索引進行初始化，即數字爲0, 1, 2, ... n，其中n是第一個數組中的元素數。

對於每個附加陣列，在矩陣中填充其列，如下所示：循環遍歷矩陣中當前列的每一行，並按如下方式計算單元格：如果前一列的相應單元格爲-1， -1轉入此單元格。否則，在當前數組中查找與前一個數組的相應行匹配的行，如果找到，則將其索引存儲到此單元格中。否則，在這個單元格中存儲-1。

對所有數組重複，即矩陣中的所有列。最後，匹配的行是矩陣最後一列沒有-1的行。

如果你真的關心效率，你可以做約翰·B建議，並寫入名爲不可改變的類，它封裝（包含一個引用）一行，並實現hashCode()和equals()。 equals()這裏可以使用Arrays.deepEquals()來實現。 Arrays中可能還有一些叫做deepHashCode()的好禮，否則你將需要自己推出。

Answer 4

1. 編寫一個接受兩個參數的方法：一個二維數組來搜索一維數組行。如果找不到匹配，該方法返回-1，否則返回匹配行的索引。

2. 對於第一個陣列的每一行： 2a。調用從第一個數組和Array2傳遞行的方法。 2b。如果2a返回> 0，則調用傳遞同一行和Array3的方法

3. 如果2b返回> 0，則輸出返回的索引。

Answer 5

AFAIK沒有內置函數。

您需要編寫自己的函數來實現它（使用for循環）。

發佈一些代碼來顯示你嘗試過什麼，如果它沒有正常工作或優化。

Answer 6

檢查這個代碼：

ArrayList<Integer[]> arr1 = new ArrayList<Integer[]>(); 
    arr1.add(new Integer[]{1,2,3}); 
    arr1.add(new Integer[]{2,2,5}); 
    arr1.add(new Integer[]{1,1,1}); 

    ArrayList<Integer[]> arr2 = new ArrayList<Integer[]>(); 
    arr2.add(new Integer[]{1,2,0}); 
    arr2.add(new Integer[]{1,2,3}); 
    arr2.add(new Integer[]{1,0,1}); 

    ArrayList<Integer[]> arr3 = new ArrayList<Integer[]>(); 
    arr3.add(new Integer[]{1,1,1}); 
    arr3.add(new Integer[]{1,2,3}); 
    arr3.add(new Integer[]{1,0,1}); 


    for (int r = 0 ; r < arr1.length() ; r++) { 
     for(int s = 0 ; s < arr2.length() ; s++){ 
      for(int t = 0 ; t < arr3.length() ; t++){ 
       if(Arrays.deepEquals(arr1.get(r), arr2.get(s))){ 

       }else 
       { 
        continue; 
       } 
       if(Arrays.deepEquals(arr1.get(r), arr3.get(t))){ 
        System.out.println(r + " " + s + " " +t);; 
       } 
      } 

     } 
    }