240.M 搜索二维矩阵 II

题目

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

示例 1：

输入：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 
输出：true 

示例 2：

输入：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 
输出：false

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= n, m <= 300

• -109 <= matix[i][j] <= 109

• 每行的所有元素从左到右升序排列

• 每列的所有元素从上到下升序排列

• -109 <= target <= 109

解题思路

类似于二分查找。

由于每行和每列都是递增的，从右上角开始遍历，我们查看某个元素时，至少可以排除掉一行或者一列。

时间复杂度：O(n+m)

实现代码

func searchMatrix(matrix [][]int, target int) bool {
	rows := len(matrix)
	cols := len(matrix[0])
	i := 0
	j := cols - 1
	for i < rows && j >= 0 {
		if matrix[i][j] == target {
			return true
		} else if matrix[i][j] < target {
			i++
		} else {
			j--
		}
	}
	return false
}