查找最大公共數

Question

我試圖編寫的代碼假設接受一個二維整數數組，對每行進行排序，然後找到行之間的最大公用數。我遇到了如何返回整數類型的問題。

目前我無法找到一種方法來取得我創建的行數組並返回它作爲整數。同樣，我知道從測試中總共會有3行，但列數量是未知的。

import java.util.Arrays; 

public class FindCommon { 

/* 
* @param a 3xN integer array, assume a is not null or empty 
* @return the largest common number among a[0], a[1], a[2], null if no common number exists 
*/ 
public static Integer getLargestCommonNumber(int[][] a) { 

    //Check if array is empty 
    if (a == null || a.length == 0){ 
     return 0; 
    } 
    //Initialize 
    int [] Row1 = a[0]; 
    int [] Row2 = a[1]; 
    int [] Row3 = a[2]; 

    Arrays.sort(a); 

    int i = 0, j = 0, k = 0; 

    // Iterate through three arrays while all arrays have elements 
    while (i < Row1.length && j < Row2.length && k < Row3.length) 
    { 
     if (Row1[i] > Row2[j] && Row2[j] > Row3[k]){ 
      System.out.print(Row1[i]+" "); 
      int max = Row1[i]; 
     } 
     else if (Row2[i] > Row1[j] && Row2[j] > Row3[k]){ 
      System.out.print(Row2[i]+" "); 
      int max = Row2[i]; 
     } 
     else if (Row3[i] > Row1[j] && Row3[j] > Row2[k]){ 
      int max = Row3[i]; 
     } 


    } 
} 
} 

我有我用來解決這個問題的測試代碼。

import org.junit.Assert; 

import org.junit.Test; 



public class FindCommonTest { 

@Test 
public void testGetLargestCommonNumber1() { 
    int[][] a = {{54, 41, 43, 55, 63}, {25, 40, 48, 12, 89}, {20, 19, 90, 94, 52}}; 
    Integer result = FindCommon.getLargestCommonNumber(a); 
    Assert.assertNull(result); 
} 

@Test 
public void testGetLargestCommonNumber2() { 
    int[][] a = {{53, 41, 43, 55, 63}, {41, 25, 48, 12, 54}, {91, 19, 90, 54, 41}}; 
    Integer result = FindCommon.getLargestCommonNumber(a); 
    Assert.assertEquals(41, (int) result); 
} 

@Test 
public void testGetLargestCommonNumber3() { 
    int[][] a = {{54, 41, 43, 55, 63}, {25, 41, 48, 12, 54}, {41, 19, 90, 54, 94}}; 
    Integer result = FindCommon.getLargestCommonNumber(a); 
    Assert.assertEquals(54, (int) result); 
} 

} 

Answer 1

回訪整數類型回來，你可以只是簡單的做到這一點：

public static Integer getLargestCommonNumber(int[][] a) { 
    //Check if array is empty 
    if (a == null || a.length == 0) { 
     return 0; 
    } 
    //Initialize 
    int[] Row1 = a[0]; 
    int[] Row2 = a[1]; 
    int[] Row3 = a[2]; 

    Arrays.sort(a); 

    int i = 0, j = 0, k = 0; 
    Integer max = null; 
    // Iterate through three arrays while all arrays have elements 
    while (i < Row1.length && j < Row2.length && k < Row3.length) { 
     if (Row1[i] > Row2[j] && Row2[j] > Row3[k]) { 
      System.out.print(Row1[i] + " "); 
      max = Row1[i]; 
     } else if (Row2[i] > Row1[j] && Row2[j] > Row3[k]) { 
      System.out.print(Row2[i] + " "); 
      max = Row2[i]; 
     } else if (Row3[i] > Row1[j] && Row3[j] > Row2[k]) { 
      max = Row3[i]; 
     } 
    } 
    return max; 
} 

Answer 2

。在你的while循環內部的邏輯問題。目前，你並沒有真正迭代三個數組。您的終止條件聽起來不錯，但截至目前它將是一個無限循環，因爲i,j,k不會改變。您應該遞增包含迭代的兩個較小數字的兩個數組的索引。此外，請確保每個陣列使用相同的索引以保持一致。不要在不同的數組之間交換索引。例如，總是使用i和Row1，總是使用j和Row2，並始終使用k和Row3。另外，你並沒有對2d數組中的每一行進行排序。您需要在每行上撥打Arrays.sort()。最後，在while循環之外聲明max。否則，您將無法返回它，因爲該變量在循環中只有一個範圍。

//Check if array is empty 
    if (a == null || a.length == 0){ 
     return 0; 
    } 
    for (int[] row : a) { 
     Arrays.sort(row); 
    } 
    //Initialize 
    int [] Row1 = a[0]; 
    int [] Row2 = a[1]; 
    int [] Row3 = a[2]; 
    int i = 0, j = 0, k = 0; 

    int max = 0; 
    // Iterate through three arrays while all arrays have elements 
    while (i < Row1.length && j < Row2.length && k < Row3.length) 
    { 
     if (Row1[i] >= Row2[j] && Row1[i] >= Row3[k]){ 
      max = Row1[i]; 
      j++; 
      k++; 
     } 
     else if (Row2[j] >= Row1[i] && Row2[j] >= Row3[k]){ 
      max = Row2[j]; 
      i++; 
      k++; 
     } 
     else if (Row3[k] >= Row1[i] && Row3[k] >= Row2[j]){ 
      max = Row3[k]; 
      i++; 
      j++; 
     } 
    } 

現在，當此循環結束時，至少有一個數組已完全遍歷。因此，可能會出現這樣的情況，仍然需要從他們離開的地方迭代兩行。爲了覆蓋所有的情況，你需要三個while循環，類似於上面的while循環遍歷其他兩行。

while(i < Row1.length && j < Row2.length) { 
    if(Row1[i] >= Row2[j]){ 
     max = Row1[i]; 
     j++; 
    } 
    else{ 
     max = Row2[j]; 
     i++; 
    } 
} 
while(i < Row1.length && k < Row3.length) { 
    if(Row1[i] > Row3[k]){ 
     max = Row1[i]; 
     k++; 
    } 
    else{ 
     max = Row3[k]; 
     i++; 
    } 
} 
while(j < Row2.length && k < Row3.length) { 
    if(Row2[j] >= Row3[k]){ 
     max = Row2[j]; 
     k++; 
    } 
    else{ 
     max = Row3[k]; 
     j++; 
    } 
} 
return max; 

最後，確保在方法結束時返回max。

Answer 3

此代碼允許您擁有幾乎任意數量的行。

public static Integer getLargestCommonNumber(int[][] a) { 

    // Check if array is empty 
    if (a == null || a.length == 0) { 
     return 0; 
    } 
    // Initialize, we are going to create a List (matrix) of Lists (rows) 
    List<List<Integer>> matrix = new ArrayList<>(); 
    for (int i = 0; i < a.length; i++) { 
     int[] aRow = a[i]; 
     List<Integer> row = new ArrayList<>(); 
     for (int j = 0; j< aRow.length; j++) { 
      row.add(aRow[j]); 
     } 
     matrix.add(row); 

    } 

    // sort the rows with largest number on the left 
    for (List<Integer> row : matrix) { 
     Collections.sort(row, new Comparator<Integer>(){ 
      @Override 
      public int compare(Integer o1, Integer o2) { 
       return -1 * o1.compareTo(o2); 
      }}); 
    } 

    // get just the first row 
    List<Integer> row0 = matrix.get(0); 
    // loop through each value in the row, from largest to smallest 
    for (Integer row0Value : row0) { 
     int count0 = 0; // this is a counter that just adds the row numbers 
     int count1 = 0; // this is a counter that adds the row numbers of rows that have a match 
     // loop through rows 2 to N 
     for(int i = 1; i < matrix.size(); i++) { 
      count0 += i; // add to the total row counter 
      if (matrix.get(i).contains(row0Value)) { 
       count1 += i; // add to counter only if there was a match in this row 
      } 
     } 
     if (count0 == count1) { // if the value is in all rows then both counters should be the same 
      return row0Value; 
     } 
    } 
    // there were no values that matched in all of the rows 
    return 0; 
}