Java:确定二维数组是否具有不连续的值

Question

我有一个问题。我在 Java 中有一个 2D 数组，我想检查该数组是否具有不连续的值。

示例:

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

上面的数组应该返回 true，因为数字 2 出现在 2 个不连续的区域(第 1 行第 2 列和第 3 行第 1 列)。

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

上面的数组应该返回 false，因为没有值出现在 2 个或更多不连续区域中。

Answer 1

检查下面的代码。评论解释了正在发生的事情。它包含三个类:ArraysMain、Index 和 IndexList(扩展了 ArrayList)。

已更新

基本上，获取所有不同的值并将它们存储在 map 中。对于每个值(如果出现多次)将有多个索引(该值在数组中的位置)。

迭代数组，将每个值的索引一一添加。如果遇到一个索引，其 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.
    }

}

}