二维数组中的查找（Java实现）
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。如在二维数组：
1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15
中，查找数字7，返回true；查找数字5，返回false.
题解:
首先，我们来谈一下最为直观的解，就是遍历一遍二维数组，时间复杂度o(n*m)，空间复杂度o(1)。当然这个时间复杂度是不足以拿offer的。我们再来看看时间复杂度为o(n)，空间复杂度微o(1)的算法。
当我们需要解决一个比较复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。
比如数组：
1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15
我们寻找7。直接的想法从左上角开始找，1小于7.那么7肯定会在1的右边或者下边。这个时候有三个区域。右边区域，下边区域和右边与下边重叠的区域，不好确定接下来该怎么搞。我们再试试从左上角开始。9大于7,那么7就只能在9的左边，不可能在9在的当前列。那么可以排除9这一列。继续找左上角，是8。8大于7排除8在的当前列。继续找左上角2。发现2小于7，那么肯定在2的下面，排除2所在的当前行。继续找左上角，找到4，发现4小于7，排除4所在的当前行。继续左上角，发现是7.找到返回。该算法每次都能排除一行或者一列。所以时间复杂度是o(n+m)，空间复杂度是o(1)。
根据题目的特点，从一个具体的案例去分析，找出优解。
package Day39; import java.util.Scanner; /** * @Author Zhongger * @Description 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序， * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 * @Date 2020.3.11 */ public class FindInMatrix { public static void main(String[] args) { int[][] matrix = new int[4][4]; int number=7; Scanner scanner = new Scanner(System.in); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { matrix[i][j]=scanner.nextInt(); } } FindInMatrix findInMatrix = new FindInMatrix(); System.out.println(findInMatrix.findInMatrix(matrix, number)); } /** * 查找方法 * @param matrix 二维数组 * @param number 待查找的数字 * @return */ private boolean findInMatrix(int[][] matrix,int number){ boolean isFind=false; int rows = matrix.length;//行数 int columns = matrix[0].length;//列数 int i=0;//行 int j=columns-1;//列 while (i<rows&&j>=0){ if (matrix[i][j]==number){ isFind=true; break; } else if (matrix[i][j]>number){ j--; } else { i++; } } return isFind; } }
剑指Offer上的原题，从今天开始我会每天更新算法题解，敬请关注
