摘要:
巧妙利用递增特性线性查找目标值。
题目
在一个 $n * m$ 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix
如下:
1 | [ |
给定 target = 5
,返回 true
。
给定 target = 20
,返回 false
。
限制:
$ 0 <= n <= 1000 $,
$ 0 <= m <= 1000 $
线性查找
从右上角开始,如果当前数比目标值小,则排除当前行;如果比目标值大,则排除当前列。
1 | // 执行用时: 28 ms |
1 | // 执行用时: 1 ms |
原题链接: 剑指Offer 04. 二维数组中的查找