esc to dismiss

240. 搜索二维矩阵 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

解体思路

这道题看上去是二分查找,但实际不那么简单。官方题解中给出了四种(包括暴力),后三种时间复杂度低的分别是 二分查找 、搜索空间缩减 和 最巧妙而复杂度也最低的方法:从左下开始遍历。下面分别看这三种:

1. 二分查找

二分查找是在一维线性数组上进行的,因此首先要将这个二维数组变成二维数组。题解的方法很简单,就是从[0, 0] 开始,因为从左到右,从上到下是递增的,因此,每次遍历都二分查找x轴 和 y轴;而每次循环元素可减去前面查找过的。

2. 搜索空间的缩减

3. 从左下角开始遍历


经验教训

略。

x