LeetCode 74. 搜索二维矩阵
题目描述
思路分析
由于矩阵的每行和每列都是有序的，我们可以将矩阵视为一个一维的有序数组，然后使用二分查找来查找目标值。
具体步骤如下：
- 将矩阵视为一个一维数组，长度为
m * n。- 使用二分查找算法，在这个一维数组中查找目标值。
- 通过计算一维数组的索引，映射回二维矩阵的行和列。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
m, n := len(matrix), len(matrix[0])
left, right := 0, m*n-1
for left <= right {
mid := left + (right-left)/2
midValue := matrix[mid/n][mid%n]
if midValue == target {
return true
} else if midValue < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
- 时间复杂度：O (log (m * n))，其中 m 和 n 分别是矩阵的行数和列数。我们使用了二分查找算法。
- 空间复杂度：O (1)，我们只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！