【LeetCode 74】算法：搜索二维矩阵
题目：给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
问题中矩阵的每一行和每一列都是有序的，给定一个目标值 target，确定这个值是否存在于矩阵中。
可以利用矩阵的有序性质，通过在每一行内进行二分查找，减少搜索空间，提高查找效率。
算法思路：
[*]从第一行开始：由于每行的第一个整数大于前一行的最后一个整数，我们可以从第一行的第一个元素开始查找。
[*]二分查找：对于每一行，使用二分查找来确定 target 是否存在于该行中。如果找到，返回 true。
[*]移动到下一行：如果当前行中没有找到 target，则由于矩阵的特性（每行的整数从左到右非严格递增排列），我们知道 target 不可能存在于该行之后的任何一行中。因此，我们可以安全地移动到下一行的第一个元素，并从那里开始新的二分查找。
[*]继续或终止：重复步骤 2 和 3，直到找到 target 或遍历完整个矩阵。
复杂度分析：
[*]时间复杂度：O(m * log n)，其中 m 是行数，n 是列数。对于每一行，最多执行一次二分查找，其时间复杂度为 O(log n)，最多遍历所有 m 行。
[*]空间复杂度：O(1)，只使用了常数额外空间。
Java代码实现：
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix.length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix.length;
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
if (matrix == target) {
return true;
} else if (matrix > target) {
col--;
} else {
row++;
}
}
return false;
}
}
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]