English
74. Search a 2D Matrix
Problem Statement
You are given an m x n
integer matrix matrix
with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
or false
otherwise.
You must write a solution in O(log(m * n))
time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 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
-104 <= matrix[i][j], target <= 104
Solution:
rs
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let (mut rows, mut cols) = (0, matrix[0].len() - 1);
while rows < matrix.len() && cols > 0 {
if matrix[rows][cols] == target {
return true;
} else if matrix[rows][cols] > target {
cols -= 1;
} else {
rows += 1;
}
}
false
}
}
...