- 题目描述
- 解题分析
- code
- 总结
题目描述
难度：中等
编写一个高效的算法来搜索 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 -10^9 <= matrix[i][j] <= 10^9 每行的所有元素从左到右升序排列 每列的所有元素从上到下升序排列 -10^9 <= target <= 10^9解题分析
这题我在剑指Offer专栏发过一篇一样的，掌握精髓之后做这个题真的很有意思。
首先看题目中最关键的一点
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
可以看出，一列中最下面的元素是这一列中最大的，一行中做左边的元素是这一行最小的。
那如果我们把左下角的元素 temp 取出 ，此时会有三种情况：
① target > temp，这说明 target 大于 temp 之上的所有元素，那么可以排除 temp 所在列
② target < temp，这说明 target 小于 temo 右边的所有元素，那么可以排除 temp 所在行
@ target = temp，即找到了答案，返回 true
按照这个逻辑不停的移动 temp 的坐标，即可找到答案.
如果取右上角的元素也是一样的道理。
codepublic boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length - 1 , column = 0; // 拿到左下角的元素 最后一行 第一列
int len = matrix[0].length;
while( row > -1 && column < len ){ // 规定范围 超出即失败
if( matrix[row][column] > target ) row--; // 左下元素大于 target 这一行元素都可以排除
else if (matrix[row][column] < target) column++;// 左下元素小于 target 这一列都可以排除
else return true;
}
return false;
}
总结
逻辑不难，理解清楚之后仔细一想其实很有意思，如果能发现题目中出现的规律并搞透彻，那么题目自然而然也就迎刃而解。再接再厉！
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂
