剑指 Offer 04. 二维数组中的查找

一、题目

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 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。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

二、题解

方法一：暴力破解

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {//判断二位数组中值为空if ((matrix == null || matrix.length == 0) || (matrix.length == 1 && matrix[0].length == 0)) {return false;}boolean res = false;for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (target == matrix[i][j]) {res = true;}}}return res;}
}

方法二：优化解法

思路：从右上角往左下角找

    /*** 优化解法* 思路：从右上角往左下角找** @param matrix* @param target* @return*/public boolean findNumberIn2DArray(int[][] matrix, int target) {//判断二维数组值为空if ((matrix == null || matrix.length == 0) || (matrix.length == 1 && matrix[0].length == 0)) {return false;}boolean res = false;int i = 0, j = matrix[0].length - 1;while (i < matrix.length && j >= 0) {if (target == matrix[i][j]) {res = true;break;} else if (target < matrix[i][j]) {j--;} else {i++;}}return res;}

剑指 Offer 03. 数组中重复的数字
剑指 Offer 04. 二维数组中的查找
剑指 Offer 05. 替换空格
剑指 Offer 06. 从尾到头打印链表
剑指 Offer 07. 重建二叉树
剑指 Offer 09. 用两个栈实现队列
剑指 Offer 10- I. 斐波那契数列
剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 11. 旋转数组的最小数字
剑指 Offer 12. 矩阵中的路径

声明：
        题目版权为原作者所有。文章中代码及相关语句为自己根据相应理解编写，文章中出现的相关图片为自己实践中的截图和相关技术对应的图片，若有相关异议，请联系删除。感谢。转载请注明出处，感谢。

By luoyepiaoxue2014

B站： https://space.bilibili.com/1523287361 点击打开链接
微博： http://weibo.com/luoyepiaoxue2014 点击打开链接