力扣最热一百题——搜索二维矩阵
目录
题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode）
题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[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]], target = 5 输出：true
示例 2：
输入：matrix = [[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]], target = 20 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
解法一：暴力不解释
- 初始化矩阵维度：
- 首先，通过
matrix.length获取矩阵的行数（即y轴的长度，记作lenY）。 - 然后，通过
matrix[0].length获取矩阵的列数（即x轴的长度，记作lenX）。这里假设矩阵至少有一行，因此matrix[0]是有效的。
- 首先，通过
- 遍历矩阵：
- 使用两层嵌套的for循环遍历矩阵的每一个元素。外层循环遍历行（y轴），内层循环遍历列（x轴）。
- 在遍历过程中，通过
matrix[y][x]访问当前遍历到的元素，并将其与目标值target进行比较。
- 查找目标值：
- 如果在某个位置
(y, x)上，当前元素matrix[y][x]等于目标值target，则表明找到了目标值，函数立即返回true。
- 如果在某个位置
- 未找到目标值：
- 如果遍历完整个矩阵后都没有找到目标值，则函数返回
false，表示目标值不在矩阵中。
- 如果遍历完整个矩阵后都没有找到目标值，则函数返回
Java写法：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 获取y轴的长度
int lenY = matrix.length;
// 获取x轴的长度
int lenX = matrix[0].length;
// 判断数组非空
if(lenY == 0 || lenX == 0){
return false;
}
// 遍历这个二维数组
for(int y = 0; y < lenY; y++){
for(int x = 0; x < lenX; x++ ){
// 如果找到了就返回true
if(target == matrix[y][x]){
return true;
}
}
}
// 上面都没找到就返回false
return false;
}
}运行时间
C++写法：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 检查矩阵是否为空
if (matrix.empty() || matrix[0].empty()) {
return false;
}
// 获取y轴的长度（行数）
int lenY = matrix.size();
// 获取x轴的长度（列数），这里假设矩阵至少有一行
int lenX = matrix[0].size();
// 遍历这个二维数组
for (int y = 0; y < lenY; y++) {
for (int x = 0; x < lenX; x++) {
// 如果找到了就返回true
if (target == matrix[y][x]) {
return true;
}
}
}
// 上面都没找到就返回false
return false;
}
};运行时间
时间复杂度以及空间复杂度
 |  |
解法二：利用自带的大小关系进行Z型走位
-
初始位置选择：由于矩阵的行和列都是有序的，从矩阵的右上角或左下角开始搜索都是可以的。这里选择从右上角开始（
x = lenX - 1, y = 0），因为这样可以同时利用行和列的排序特性。 -
搜索逻辑：
- 如果当前元素
matrix[y][x]等于目标值target，则直接返回true，因为找到了目标。 - 如果当前元素小于目标值
target，则由于当前行是从左到右递增的，我们可以确定目标值不可能在当前行的左侧（即更小的数），因此将y（行索引）增加，向下移动到下一行继续搜索。 - 如果当前元素大于目标值
target，则由于当前列是从上到下递增的，我们可以确定目标值不可能在当前列的下方（即更大的数），因此将x（列索引）减少，向左移动到前一列继续搜索。
- 如果当前元素
-
循环终止条件：当
x小于0或y大于等于lenY时，循环终止。这是因为x代表列索引，其有效范围是[0, lenX-1]；而y代表行索引，其有效范围是[0, lenY-1]。如果x变为负数或y超出范围，说明已经搜索了矩阵的所有可能位置，但都没有找到目标值。 -
返回结果：如果在循环过程中找到了目标值，则返回
true；如果循环结束后仍未找到目标值，则返回false。
这种搜索策略非常的有效，因为它利用了矩阵的行和列排序特性，通过每次比较后只排除一行或一列的可能性，从而减少了搜索空间。
Java写法：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 由于数组是有序的，我们可以利用这个特性
// 获取x，y轴方向上的长度
int lenX = matrix[0].length;
int lenY = matrix.length;
// 从右上角开始寻找
int x = lenX - 1;
int y = 0;
// 寻找逻辑
while(x >= 0 && y < lenY){
// 发现目标返回true
if(matrix[y][x] == target){
return true;
}
// 由于我们是从右上角开始寻找的
// 它的左边的数比他小，他下边的数比他大
// 所以这里如果比target小，就往下找大的数
if(matrix[y][x] < target){
y++;
}else{
// 相反，这里比target大，就往左找小的数
x--;
}
}
// 如果最后还是没找到就返回false
return false;
}
}运行时间
C++写法
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 获取x，y轴方向上的长度
int lenX = matrix[0].size();
int lenY = matrix.size();
// 从右上角开始寻找
int x = lenX - 1;
int y = 0;
// 寻找逻辑
while (x >= 0 && y < lenY) {
// 发现目标返回true
if (matrix[y][x] == target) {
return true;
}
// 由于我们是从右上角开始寻找的
// 它的左边的数比他小，他下边的数比他大
// 所以这里如果比target小，就往下找大的数
if (matrix[y][x] < target) {
y++;
} else {
// 相反，这里比target大，就往左找小的数
x--;
}
}
// 如果最后还是没找到就返回false
return false;
}
};运行时间
时间复杂度以及空间复杂度
总结
总结来说就是暴力梭哈一切，冷静思考获得新生
原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/142416063
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！