前言
真菜的我。
正文
问题来源
本问题来自leetcode上的74题。用go语言做的
问题描述
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
分析：
本人的想法是采用二分搜索来查找，首先根据行二分找到具体行，然后根据列二分找到具体值。 本人写的Go代码如下：
func searchMatrix(matrix [][]int, target int) bool {
rowb := 0
l := len(matrix)
rowe := l - 1
rowm := (rowb + rowe)/2
if l == 0 {
return false
}
for ; rowe > rowb; rowm = (rowb+rowe)/2 {
cur := matrix[rowm][0]
if target == cur {
return true
} else if target > cur {
next := rowm + 1
if (next<l)&&(target>=matrix[next][0]) {
rowb = rowm + 1
} else {
break
}
} else {
rowe = rowm - 1
}
fmt.Printf("b:%d e:%d\n",rowb, rowe)
}
colb := 0
cole := len(matrix[0]) - 1
colm := (colb + cole) / 2
for ; colb <= cole ; colm = (colb+cole)/2 {
cur := matrix[rowm][colm]
if target == cur {
return true
} else if target > cur {
colb = colm + 1
} else {
cole = colm - 1
}
}
return false
}
这题的思路很简单，利用矩阵行列分别有序的性质，我们从第0行的最右端开始搜索，两种情况：
- 如果当前的数比target大，则说明target必然在target的左边，则搜索其左边的位置
- 如果当前的数比target小，则说明和target相等的数必然不在这一行，因此往下一行搜索。
- 如果当前的数和target相等，则说明找到了这个target
func searchMatrix(matrix [][]int, target int) bool {
n := len(matrix)
if n <= 0 {
return false
}
m := len(matrix[0])
if m <= 0 {
return false
}
for i, j := 0, m - 1; i < n && j >= 0; {
num := matrix[i][j]
if num == target {
return true
} else if num < target {
i++
} else {
j--
}
}
return false
}
总结：
勤思考
结语
不管怎么样好好加油。
