74. 搜索二维矩阵
74. Search a 2D Matrix
题目描述
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性:
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
LeetCode74. Search a 2D Matrix中等
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
Java 实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row, col;
if (matrix == null || (row = matrix.length) == 0 || (col = matrix[0].length) == 0) {
return false;
}
int k = row * col;
int i = 0, j = k, m;
while (i < j) {
m = i + (j - i) / 2;
if (matrix[m / col][m % col] == target) {
return true;
} else if (matrix[m / col][m % col] < target) {
i = m + 1;
} else {
j = m;
}
}
return false;
}
}
相似题目
参考资料