题目
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例1
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
思路
给的数组其实是整体有序的,行内升序,列内升序,行与行之间也是升序。
其实一开始直接想到的就是先确定target是属于哪个行,也就是从第一列中查找target;然后在找到的行中,再继续查找target。
要想进行高效查找的话,那就是二分查找了。
另外,其实整个数据全局有序,也可以进行全局的二分搜索。
先查列,再查行
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int line = -1;
for (int i = 0; i < matrix.length; i++) {
if (target >= matrix[i][0]) {
line = i;
} else {
break;
}
}
if (line == -1) {
return false;
}
for (int j = 0; j < matrix[line].length; j++) {
if (target == matrix[line][j]) {
return true;
} else if (target < matrix[line][j]) {
return false;
}
}
return false;
}
}
因为是线性查找,没有用到二分搜索,所以时间复杂度是O(m+n)
二分法
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length < 1 || matrix[0].length < 1 || target < matrix[0][0]) return false;
int lineLow = 0, lineHigh = matrix.length - 1;
while (lineLow < lineHigh) {
int lineMid = (lineHigh + lineLow + 1) / 2;
if (matrix[lineMid][0] == target) {
return true;
} else if (matrix[lineMid][0] > target) {
lineHigh = lineMid - 1;
} else {
lineLow = lineMid;
}
}
int rowLow = 0, rowHigh = matrix[lineLow].length - 1;
while (rowLow <= rowHigh) {
int rowMid = (rowLow + rowHigh) / 2;
if (target == matrix[lineLow][rowMid]) {
return true;
} else if (target > matrix[lineLow][rowMid]) {
rowLow = rowMid + 1;
} else {
rowHigh = rowMid -1;
}
}
return false;
}
}
时间复杂度:O(log m + log n) = O (log mn)
全局二分
这个可以参考官方解法
时间复杂度:O (log mn)
边界值问题
其实这个题的思路并不难,但是做这种题目,总是对于边界值、终止条件和演进方向不能有很清晰的思路,做一下经验总结。
首先,我们会先拿到两端的索引,然后计算中间索引,对中间索引指向的内容进行判断。
-
中间索引的计算方法
上面的代码,使用的是(low + high) / 2,这个方法其实不是很好,如果两个数字都很大的话,是有可能会出现越界的。
最好的方法是 low + (high - low) / 2
-
中间索引的偏向问题
使用 low + (high - low) /2 的计算方法,其实算出来的mid值会偏向low,如果我们想让high侧的内容优先进行判断,应该采用:
low + (high - low + 1) / 2
-
终止条件
终止条件需要考虑的是low是否应该等于high。
如果循环条件是low<high, 也就是终止条件为low>=high。终止条件其实是跟中间索引的计算方法和计算目标有关系的。如果是low>=high进行终止的话,其实是有可能会存在最终low指向的位置没有进行校验的。
如果要确保所有的索引位置都进行过校验,循环条件应该设置为low<=high,这样终止条件就是low>high。
感觉还是没有论证清楚,后续再补充。当前的经验是:终止条件需要考虑相等的情况,最终的返回结果需要是符合预期的。
-
指针的演进方向
比较完mid指针后,low和high指针需要考虑是赋mid的值,还是mid±1
这个其实还是比较好确定的,就是mid这个值在判断完之后,如果已经不是符合预期的数据,那就应该使用±1,否则就不能±1。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)