# | Title | Difficulty | Topic |
---|---|---|---|
240 | Search a 2D Matrix II | Medium | Binary Search; Divide and Conquer |
Description
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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
1 |
[ |
Given target = 5
, return true
.
Given target = 20
, return false
.
Search
从数组的右上角开始,如果matrix[row][col] > target
,则col--
;若matrix[row][col] < target
,则row++
。因为,matrix[row][col] > target
,则[col, n)
的列都比target大;matrix[row][col] < target
,则[0, row]
的行都比target小。
1 |
class { |
因为每次扫描不是向左就是向下,因此时间复杂度为$$O(m+n)$$。
近期评论