我正试图在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总是返回匹配。我对函数的理解是错误的吗?
发布于 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;
}
https://stackoverflow.com/questions/52807139
复制相似问题