<分区>
这是最近编码面试的问题
编写一个高效的算法来搜索 m x n 矩阵中的值。
此矩阵具有以下属性:
每行中的整数从左到右升序排列。
每列中的整数从上到下升序排列。
.[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10, 13, 14, 17, 24] [18, 21, 23, 26, 30]
有没有办法在 O(mn) 以下执行此操作。我看不出如何对该数组进行二进制搜索，因为无法消除任何内容。
<分区>
这是最近编码面试的问题
编写一个高效的算法来搜索 m x n 矩阵中的值。
此矩阵具有以下属性:
每行中的整数从左到右升序排列。
每列中的整数从上到下升序排列。
.
[1, 4, 7, 11, 15]
[2, 5, 8, 12, 19]
[3, 6, 9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]
有没有办法在 O(mn) 以下执行此操作。我看不出如何对该数组进行二进制搜索，因为无法消除任何内容。
最佳答案
您可以使用这个简单的算法，它利用了这样一个事实，即在具有这些属性的矩阵中，mtx[i][j] 的值总是小于任何值mtx[x][y]，其中 x > i 或 y > j，换句话说，向右和向下的任何值:
public static boolean find(int[][] mtx, int val) {
int maxCol = mtx[0].length, minCol = 0;
for(int i = 0 ; i < mtx.length ; i++) {
for(int j = minCol ; j < maxCol ; j++) {
if(val == mtx[i][j]) return true;
if(val < mtx[i][j]) {
maxCol = j;
break;
}
}
if(maxCol == 0) break;
minCol = 0;
if(i != mtx.length-1 && val > mtx[i+1][maxCol-1]) minCol = maxCol-1;
}
return false;
}
想法是逐行搜索，如果找到更大的值，则可以停止在该行中查找，并且您知道不必在以后的行中搜索超出该列的内容。如果一行的第一个值大于该值，则可以停止搜索并返回 false。此外，在每行搜索结束时，您检查下一行的单元格 maxCol-1，如果值较大，则在下一个循环中，您可以跳过前面的每个单元格。
最坏的情况是最大值(或更大)，复杂度为 O(m+n)，因为它会检查所有第一行，然后跳过接下来的 m 行。
关于java - 在亚线性时间搜索二维数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36815652/