给定一个矩阵(即数组的数组)，通过删除指定的行和列找到它的子矩阵
给定一个矩阵(即数组的数组)，通过删除指定的行和列找到它的子矩阵
提问于 2018-10-15 05:12:31
我正试图在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总是返回匹配。我对函数的理解是错误的吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-10-15 06:02:36
您的想法是正确的，并且binarySearch不应该施加任何显著的性能损失。但是，每当遇到不应包含在输出中的行(即binarySearch返回>= 0)时，内循环或外循环都将完全中断，并忽略应包含在结果数组中的任何后续行或列。在您的示例中，如果为i == 1，则对rowsToDelete的binarySearch调用将返回>= 0并过早地中断外部循环。
就边缘情况而言，编写一个不假定(或强制)要排序的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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52807139
复制相关文章
相似问题