题目描述
Write an efficient algorithm that searches for a value in an
m x n
matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
例子
例子 1
Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output:true
例子 2
Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output:false
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
解题思路
由于矩阵每一行都是有序的,且每一行都比上一行大,因此思路很明确,可以使用两次二分查找,第一次找到有可能包含目标元素的行(首元素比目标值小,且下一行首元素比目标值大),第二次在该行查找该元素即可,代码如下:
1 |
|
- 时间复杂度:
O(log max(m,n))
- 空间复杂度:
O(1)
GitHub 代码同步地址: 74.SearchA2DMatrix.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions