74. Search a 2D Matrix
程序员文章站
2022-07-14 17:53:51
...
Description
https://leetcode.com/problems/search-a-2d-matrix/
在一个二维矩阵中,查找某个元素是否存在。
- 矩阵每行从小到大排列
- 矩阵每列从小到大排列
Solving Ideas
把矩阵看作一维的已排序的数组,使用 二分查找算法 进行搜索。
时间复杂度:
空间复杂度:
Solution
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int rows = matrix.length, cols = matrix[0].length;
int begin = 0, end = rows * cols - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
int midVal = matrix[mid / cols][mid % cols];
if (midVal == target) return true;
if (midVal < target) begin = mid + 1;
else end = mid - 1;
}
return false;
}
}
《剑指offer》二维数组中的查找
时间复杂度:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int i = 0, j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] > target) j--;
else i++;
}
return false;
}
}
推荐阅读
-
LeetCode 74. Search a 2D Matrix
-
74. Search a 2D Matrix
-
74. Search a 2D Matrix
-
LeetCode 74. Search a 2D Matrix
-
[leetcode]74. Search a 2D Matrix
-
leetcode -- 74. Search a 2D Matrix
-
LeetCode 74. Search a 2D Matrix
-
[leetcode] 74. Search a 2D Matrix @ python
-
[leetcode]74. Search a 2D Matrix
-
74. Search a 2D Matrix