Description#
Write an efficient algorithm that searches for a value target in an m x n integer matrix 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 1:
Input: 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
Output: true
Example 2:
Input: 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
Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
| class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
j = bisect_left(row, target)
if j < len(matrix[0]) and row[j] == target:
return True
return False
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (var row : matrix) {
int j = Arrays.binarySearch(row, target);
if (j >= 0) {
return true;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (auto& row : matrix) {
int j = lower_bound(row.begin(), row.end(), target) - row.begin();
if (j < matrix[0].size() && row[j] == target) {
return true;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
| func searchMatrix(matrix [][]int, target int) bool {
for _, row := range matrix {
j := sort.SearchInts(row, target)
if j < len(matrix[0]) && row[j] == target {
return true
}
}
return false
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function searchMatrix(matrix: number[][], target: number): boolean {
const n = matrix[0].length;
for (const row of matrix) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && row[left] == target) {
return true;
}
}
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| use std::cmp::Ordering;
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let m = matrix.len();
let n = matrix[0].len();
let mut i = 0;
let mut j = n;
while i < m && j > 0 {
match target.cmp(&matrix[i][j - 1]) {
Ordering::Less => {
j -= 1;
}
Ordering::Greater => {
i += 1;
}
Ordering::Equal => {
return true;
}
}
}
false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| /**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const n = matrix[0].length;
for (const row of matrix) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && row[left] == target) {
return true;
}
}
return false;
};
|
1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
foreach (int[] row in matrix) {
int j = Array.BinarySearch(row, target);
if (j >= 0) {
return true;
}
}
return false;
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
i, j = m - 1, 0
while i >= 0 and j < n:
if matrix[i][j] == target:
return True
if matrix[i][j] > target:
i -= 1
else:
j += 1
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := m-1, 0
for i >= 0 && j < n {
if matrix[i][j] == target {
return true
}
if matrix[i][j] > target {
i--
} else {
j++
}
}
return false
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function searchMatrix(matrix: number[][], target: number): boolean {
let m = matrix.length,
n = matrix[0].length;
let i = m - 1,
j = 0;
while (i >= 0 && j < n) {
let cur = matrix[i][j];
if (cur == target) return true;
if (cur > target) {
--i;
} else {
++j;
}
}
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
int m = matrix.Length, n = matrix[0].Length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
}
|
