最大公約数を見つける

Question

私が書いてみたいコードは、整数の2次元配列を受け取り、各行をソートしてから、行間の最大公約数を見つけることを想定しています。整数型を返す方法に関する問題に取り組んでいます。

現在、私が作成した行配列を取得して整数に戻す方法はありません。同様に、私は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

整数型バック返すために、あなたは、単にこれを行うことができます：あなたのwhileループ内のロジックで問題が

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

があります。現在、3つの配列を実際に繰り返しているわけではありません。あなたの終了条件は正しく聞こえますが、現在はi、j、kは変更されないため、無限ループになります。反復される2つの小さい数字を含む2つの配列のインデックスをインクリメントする必要があります。また、配列ごとに同じインデックスを使用して一貫性があることを確認してください。異なる配列間でインデックスを交換しないでください。たとえば、常にiとRow1を使用し、常にjとRow2を使用し、常にkとRow3を使用します。さらに、2d配列の各行を正しく並べ替えるわけでもありません。各行でArrays.sort()に電話する必要があります。最後に、maxをwhileループの外に宣言します。変数がループ内にスコープを持つだけなので、変数を返すことはできません。

//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++; 
     } 
    } 

このループが終了すると、少なくとも1つの配列が完全にトラバースされています。したがって、2つの行が途中から中断された箇所から繰り返し処理される必要がある場合があります。すべてのケースをカバーするには、他の2つの行の残りの部分を反復するために、上記のものと同様の3つの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; 
}