java - 给定一个矩阵(即数组的数组)，求其删除指定行和列得到的子矩阵

Question

我正在尝试解决 CodeSignal 上的这一编码挑战。

Example

    For matrix = [[1, 0, 0, 2], 
              [0, 5, 0, 1], 
              [0, 0, 3, 5]]
    rowsToDelete = [1], and columnsToDelete = [0, 2], 
the output should be[[0, 2],[0, 5]]

这是我的代码:

    int[][] constructSubmatrix(int[][] matrix, int[] rowsToDelete, int[] columnsToDelete) {
        int numRows = matrix.length;
        int numCols = matrix[0].length;
        int numRowsToDelete = rowsToDelete.length;
        int numColsToDelete = columnsToDelete.length;
        int[][] newMatrix = new int[numRows-numRowsToDelete][numCols-numColsToDelete];
        int i1=0; 
        for(int i=0; (i<numRows) && (Arrays.binarySearch(rowsToDelete,i)<0); i++) {
            int j1=0;
            for(int j=0; (j<numCols) && (Arrays.binarySearch(columnsToDelete,j)<0); j++) {
                newMatrix[i1][j1]=matrix[i][j];
                j1++;
            }
            i1++;
        }
        return newMatrix;
    }

我做错了什么吗？

但是我正在获取输出:

[[0,0], 
 [0,0]]

我相信这是因为 Arrays.binarySearch 总是返回匹配项。我对这个功能的理解有误吗？

Answer 1

您的想法是正确的，binarySearch 不应造成任何显着的性能损失。但是，每当遇到不应包含在输出中的行(即 binarySearch 返回 >= 0)时，内循环或外循环将完全中断并忽略任何应该包含在结果数组中的后续行或列。在您的示例中，当 i == 1 时，对 rowsToDelete 的 binarySearch 调用返回 >= 0 并中断外循环过早。

就边缘情况而言，编写一个不假定(或强加)要排序的 ToDelete 数组的函数是合理的。此外，如果 ToDelete 数组包含重复项，输出将包含额外的行。

考虑到所有这些，Set 是执行行/列包含快速检查的最佳数据结构，并且适用于可能未排序或包含重复项的参数数组。这是一个完整的、有效的示例:

int[][] constructSubmatrix(int[][] matrix, int[] rowsToDelete, int[] columnsToDelete) {
    Set<Integer> rowsDel = new HashSet<>();
    Set<Integer> colsDel = new HashSet<>();

    for (int e : rowsToDelete) { rowsDel.add(e); }
    for (int e : columnsToDelete) { colsDel.add(e); }

    int[][] newMatrix = new int[matrix.length-rowsDel.size()]
                               [matrix[0].length-colsDel.size()];

    for (int i = 0, newI = 0; i < matrix.length; i++) {
        if (!rowsDel.contains(i)) {
            for (int j = 0, newJ = 0; j < matrix[i].length; j++) {
                if (!colsDel.contains(j)) {
                    newMatrix[newI][newJ++] = matrix[i][j];
                }
            }

            newI++;
        }
    }

    return newMatrix;
}

Try it!