Java：2D配列に不連続な値があるかどうかを調べる

Question

質問があります。私はJavaで2D配列を持っており、配列に値がないかどうかをチェックしたい。

例：

True: 
1 2 3 3 
1 4 4 5 
2 6 6 5 
7 7 8 8 

上記アレイは2つの不連続領域における番号2表示される（行1 COL 2及び行3 COL 1）ので、trueを返すべきです。

False: 
1 2 3 3 
1 4 4 5 
6 7 7 5 
8 8 9 9 

2つ以上の不連続な領域に表示される値がないため、上記の配列はfalseを返す必要があります。

Answer 1

は、本質的に、我々は、グループに各アレイ値場所を必要とします。すべてのポジションを知ったら、これらのポジションがすべて隣接しているかどうかを調べる必要があります（pos1ごとにpos2、pos1、pos2）。< 2）。 JUnitテストとともに

public class ContiguousArray { 

    public static <E> boolean isContiguous(E[][] array) { 
     Map<E, Collection<Integer[]>> groupedPositions = groupLocations(array); 

     return groupedPositions.values().stream().allMatch(ContiguousArray::allContiguous); 
    } 

    private static <E> Map<E, Collection<Integer[]>> groupLocations(E[][] array) { 
     Map<E, Collection<Integer[]>> locations = new HashMap<>(); 

     for(int x = 0; x < array.length; x++) { 
      for(int y = 0; y < array[x].length; y++) { 

       Collection<Integer[]> knownIndices; 
       Integer[] currentPosition = new Integer[] { x, y }; 
       E currentElement = array[x][y]; 

       if(locations.containsKey(currentElement)) { 
        knownIndices = locations.get(currentElement); 
       } else { 
        knownIndices = new HashSet<>(); 

        locations.put(currentElement, knownIndices); 
       } 
       knownIndices.add(currentPosition); 
      } 
     } 
     return locations; 
    } 

    /** 
    * @return true, if all of the provided indices have an adjacent index in 
    *   the same collection. Also true, if the collection's size < 2. 
    *   False, otherwise. 
    */ 
    private static boolean allContiguous(Collection<Integer[]> indices) { 
     return indices.stream().allMatch(thisIndex -> hasAdjacent(indices, thisIndex) || indices.size() < 2); 
    } 

    private static boolean hasAdjacent(Collection<Integer[]> indices, Integer[] thisIndex) { 
     return indices.stream().anyMatch(thatIndex -> isAdjacent(thisIndex, thatIndex)); 
    } 

    private static boolean isAdjacent(Integer[] thisIndex, Integer[] thatIndex) { 
     return thatIndex != thisIndex && calculateDistance(thisIndex, thatIndex) < 2; 
    } 

    private static int calculateDistance(Integer[] indexA, Integer[] indexB) { 
     int sum = 0; 

     for (int i = 0; i < indexA.length; i++) { 
      sum += Math.abs(indexA[i] - indexB[i]); 
     } 
     return sum; 
    } 
} 

：

public class ContiguousArrayTest { 
    @Test 
    public void test() { 
     assertFalse(ContiguousArray.isContiguous(new Integer[][] { 
      { 1, 2, 3, 3 }, 
      { 1, 4, 4, 5 }, 
      { 2, 6, 6, 5 }, 
      { 7, 7, 8, 8 } 
     })); 

     assertFalse(ContiguousArray.isContiguous(new Character[][] { 
      { 'a', 'b' }, 
      { 'b', 'a' }, 
     })); 

     assertTrue(ContiguousArray.isContiguous(new Character[][] { 
      { 'a', 'a', 'a' }, 
      { 'b', 'a' }, 
      { 'b' }, 
     })); 

     assertTrue(ContiguousArray.isContiguous(new Integer[][] { 
      { 1, 2, 3, 3 }, 
      { 1, 4, 4, 5 }, 
      { 6, 7, 7, 5 }, 
      { 8, 8, 9, 9 } 
     })); 

     assertTrue(ContiguousArray.isContiguous(new Integer[][] { 
      { 1, 2, 3, 3 }, 
      { 1, 1, 4, 5 }, 
      { 6, 1, 7, 5 }, 
      { 8, 8, 9, 9 } 
     })); 

     assertTrue(ContiguousArray.isContiguous(new Integer[][] { 
      { 1, 2 }, 
      { 2, 2 } 
     })); 
    } 
} 

Answer 2

以下のコードを確認してください。コメントは何が起こっているのかを説明します。 ,IndexおよびIndexListの3つのクラスが含まれており、それぞれArrayListになります。

を更新し

基本的には、すべての個別の値を取得し、マップに格納します。各値（複数回表示される場合）には、複数のインデックス（配列内の値の位置）があります。

各値のインデックスを1つずつ追加して配列を反復処理します。 rowIndexが他のすべてのインデックスのrowIndexと一致せず、現在の値に対してcolumnIndexと同じインデックスを取得した場合、その値は不連続です。ここ

public class ArraysMain { 

private static final int[][] values = {{1, 2, 3, 3}, {1, 4, 4, 5}, {2, 6, 6, 5}, {7, 7, 8, 8}}; 
// private static final int[][] values = {{1, 2, 3, 3}, {1, 4, 4, 5}, {6, 7, 7, 5}, {8, 8, 9, 9}}; 

public static void main(String[] args) { 
    System.out.println("Has Discontigous: " + hasDiscontigous()); 
} 

public static boolean hasDiscontigous() { 
    // Initialize a map to hold the indexes for each int found 
    // For example the value 3 will be mapped to the indexes as shown below 
    // (3) -> [0,2], [0,3] 
    // (4) -> [1,1], [1,2] 
    Map<Integer, IndexList<Index>> map = new HashMap<>(); 

    // Iterate through the int array and add the indexes per the value 
    for (int i = 0; i < values.length; i++) { 
     // Get the i-th row 
     int[] row = values[i]; 

     // Iterate through the current row values and add them to the map with the corresponding indexes 
     for (int j = 0; j < row.length; j++) { 
      // If the map does not contain the j-th value then that value has not been added yet so 
      // Initialize the List 
      if (!map.containsKey(row[j])) { 
       // Initialize the list 
       map.put(row[j], new IndexList<>()); 
      } 

      // Get the value's indexes list and add this value's index 
      // If the value is added to the list, 'true' is returned 
      boolean add = map.get(row[j]).add(new Index(i, j)); 

      if (!add) { 
       // If false means a discontiguous value has been found 
       System.out.println("Value: " + values[i][j] + " is discontigous"); 
       return true; 
      } 
     } 
    } 

    return false; 
} 

/** 
* This will hold the indexes i.e rowIndex and columnIndex 
*/ 
public static class Index { 

    private int rowIndex; 
    private int columnIndex; 

    public Index(int rowIndex, int columnIndex) { 
     this.rowIndex = rowIndex; 
     this.columnIndex = columnIndex; 
    } 

    public int getRowIndex() { 
     return rowIndex; 
    } 

    public void setRowIndex(int rowIndex) { 
     this.rowIndex = rowIndex; 
    } 

    public int getColumnIndex() { 
     return columnIndex; 
    } 

    public void setColumnIndex(int columnIndex) { 
     this.columnIndex = columnIndex; 
    } 

} 

/** 
* Extend the {@code ArrayList} object and override the add() method 
* @param <T> 
*/ 
public static class IndexList<T> extends ArrayList<Index> { 

    /** 
    * This method determines if a discontigous value has been found. If a value is not discontigous it's indexes are added to the list, 
    * if not, this method returns false 
    * @param e 
    * @return 
    */ 
    @Override 
    public boolean add(Index e) { 
     // Before adding an index object ensure the row or column do not match 

     for (Index thi : this) { 
      // Check if the rows match 
      if (e.rowIndex != thi.rowIndex && e.columnIndex != thi.columnIndex) { 
       // If the rowIndex and columnIndex do not match then don't add the value 
       return false; 
      } 

     } 

     return super.add(e); //To change body of generated methods, choose Tools | Templates. 
    } 

} 

}

Answer 3

別solutoinあります。理解しやすいビットですが、最適化が必要です。

更新：これは、各値が不連続かどうかをチェックし、そうであれば1つまたは複数の値をチェックします。

public class CheckIfDiscontiguous { 
public static void main(String args []){ 
    CheckIfDiscontiguous so = new CheckIfDiscontiguous(); 
    int[][] input = {{1,2,3,3}, {1,4,4,5}, {2,7,7,5}, {8,8,9,9}}; 
    System.out.println(so.discontiguousValueCheck(input)); 
} 
public boolean discontiguousValueCheck(int[][] input){ 
    int m=4; 
    int n=4; 
    int flag = 0; 
    int count = 1; 
    int discontiguousCount = 1; 
    int[] discontiguousSuspects = new int[16]; 
    int index = 0; 
    for(int i=0; i<4; i++){ 
     for(int j=0; j<4; j++){ 

      //check for 1st row starts 
      //check for (0,0) 
      if(i==0 && j==0){  
       if(!(input[0][0]==input[0][1] || input[0][0]==input[1][0])){ 
        discontiguousSuspects[index] = input[0][0]; 
       } 
      } 
      //check for (0,1) 
      if(i==0 && j==1){ 
       if(!(input[0][1]==input[0][0] || input[0][1]==input[0][2] || input[0][1]==input[1][1])){ 
        //System.out.println("goes"); 
        discontiguousSuspects[index] = input[0][1]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[0][1]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (0,2) 
      if(i==0 && j==2){ 
       if(!(input[0][2]==input[0][1] || input[0][2]==input[0][3] || input[0][2]==input[1][2])){ 
        discontiguousSuspects[index] = input[0][2]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[0][2]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (0,3) 
      if(i==0 && j==3){ 
       if(!(input[0][3]==input[0][2] || input[0][3]==input[1][3])){ 
        discontiguousSuspects[index] = input[0][3]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[0][3]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for 1st row ends 

      //check for 2nd row elements start 
      //check for (1,0) 
      if(i==1 && j==0){  
       if(!(input[1][0]==input[0][0] || input[1][0]==input[2][0] || input[1][0]==input[1][1])) { 
        discontiguousSuspects[index] = input[1][0]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[1][0]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (1,1) 
      if(i==1 && j==1){ 
       if(!(input[1][1]==input[1][0] || input[1][1]==input[0][1] || input[1][1]==input[1][2] || input[1][1]==input[2][1])){ 
        discontiguousSuspects[index] = input[1][1]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[1][1]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (1,2) 
      if(i==1 && j==2){ 
       if(!(input[1][2]==input[1][1] || input[1][2]==input[0][2] || input[1][2]==input[1][3] || input[1][2]==input[2][2])){ 
        discontiguousSuspects[index] = input[1][2]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[1][2]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (1,3) 
      if(i==1 && j==3){ 
       if(!(input[1][3]==input[1][2] || input[1][3]==input[0][3] || input[1][3]==input[2][3])){ 
        discontiguousSuspects[index] = input[1][3]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[1][3]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 

      //check for 2nd row elements end 


      //check for 3rd row elements start 
      //check for (2,0) 
      if(i==2 && j==0){  
       if(!(input[2][0]==input[1][0] || input[2][0]==input[3][0] || input[2][0]==input[2][1])) { 
        count++; 
        discontiguousSuspects[index] = input[2][0]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[2][0]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
           discontiguousCount++; 
          } 
         } 
        } 
       } 
      } 
      //check for (2,1) 
      if(i==2 && j==1){ 
       if(!(input[2][1]==input[2][0] || input[2][1]==input[1][1] || input[2][1]==input[2][2] || input[2][1]==input[3][1])){ 
        discontiguousSuspects[index] = input[2][1]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[2][1]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (2,2) 
      if(i==2 && j==2){ 
       if(!(input[2][2]==input[2][1] || input[2][2]==input[1][2] || input[2][2]==input[2][3] || input[2][2]==input[3][2])){ 
        discontiguousSuspects[index] = input[2][2]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[2][2]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (2,3) 
      if(i==2 && j==3){ 
       if(!(input[2][3]==input[2][2] || input[2][3]==input[1][3] || input[2][3]==input[3][3])){ 
        discontiguousSuspects[index] = input[1][3]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[2][3]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 

      //check for 3rd row elements end 

      //check for 4th row starts 
      //check for (3,0) 
      if(i==3 && j==0){  
       if(!(input[3][0]==input[3][1] || input[3][0]==input[2][0])){ 
        discontiguousSuspects[index] = input[3][0]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[2][3]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (3,1) 
      if(i==3 && j==1){ 
       if(!(input[3][1]==input[3][0] || input[0][1]==input[3][2] || input[3][1]==input[2][1])){ 
        discontiguousSuspects[index] = input[3][1]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[3][1]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (3,2) 
      if(i==3 && j==2){ 
       if(!(input[3][2]==input[3][1] || input[3][2]==input[3][3] || input[3][2]==input[2][2])){ 
        discontiguousSuspects[index] = input[3][2]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[3][2]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for (3,3) 
      if(i==0 && j==3){ 
       if(!(input[3][3]==input[3][2] || input[3][3]==input[2][3])){ 
        discontiguousSuspects[index] = input[3][3]; 
        index++; 
        if(discontiguousSuspects.length>=2){ 
         for(int k = 0; k<discontiguousSuspects.length; k++){ 
          if(discontiguousSuspects[k]==input[3][3]){ 
           if(discontiguousCount==2){ 
           return true; 
           } 
          } 
         } 
        } 
       } 
      } 
      //check for 3rd row ends 

     } 
    } 
    return false; 
} 

}