力扣最热一百题——搜索二维矩阵

题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode）

题目描述

解法一：暴力不解释

Java写法：

运行时间

C++写法：

运行时间

时间复杂度以及空间复杂度

解法二：利用自带的大小关系进行Z型走位

Java写法：

运行时间

C++写法

运行时间

时间复杂度以及空间复杂度

总结

题目链接：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.length
n == matrix[i].length
1 <= 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++ ){// 如果找到了就返回trueif(target == matrix[y][x]){return true;}}}// 上面都没找到就返回falsereturn 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){// 发现目标返回trueif(matrix[y][x] == target){return true;}// 由于我们是从右上角开始寻找的// 它的左边的数比他小，他下边的数比他大// 所以这里如果比target小，就往下找大的数if(matrix[y][x] < target){y++;}else{// 相反，这里比target大，就往左找小的数x--;}}// 如果最后还是没找到就返回falsereturn 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;  }  
};