剑指offer第一题

没错，又开始刷剑指offer了这一次可能是最认真的一次了，因为真的不想去做运维了，准备一个月刷完吧！

第一题

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

这是从牛客网上找的剑指offer的题目 首先我们们开始分析这个题，其实这个题目我从很早之前就做过了，首先我们可以先通过读题来获取一部分内容。

题目分析

首先呢，我们可以总结一下这个题目，其中的意思就是说让我们在一个二维数组中寻找一个数，其次二维数组其实是有规律的，就是大小从左往右依次变大，从上往依次次变大。 从解法上来分析首先可以想到的是暴力法，就是直接二重循环就完了，直接暴力，但是这是为了我们的算法我们要考虑更加简便的方法。 首先，这个二位数组是有规律的，同一行的大小是右边最大，左边最小，同一列是上面最小下面最大，所以我们可以通过选定一个角的方式来进行遍历，例如说右上角，因为这个角落比他大的话就是向下走，比他小的话就是想左走，所以说我们还可以选择左下角一样的道理。 其次就是开始运算了，如果是比他大，就向下走，如果是比他小就想左走，然后开始逐步便利即可。

代码书写

暴力法

public class One { public static void main(String[] args) { One one=new One(); int arr[][]={}; System.out.println(one.find(16, arr)); } public boolean find(int target, int [][] array) { if(array.length==0 || array[0].length==0){ return false; } if(target<array[0][0]){ return false; } for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[i].length; j++) { int item = array[i][j]; if(item==target){ return true; } } } return false; } }

代码非常的简单，我就不在过多的解释了我就简要的说几点。

第一在书写算的时候第一步一定是不要忘记边缘的计算，这是很重要的第二要善于使用return，break等条件结束语句便于我们节省一些复杂度

简要的说一下代码： 首先第一步是判断空值，如果穿传进来的数组是空的下面所有的有关数组的判断都会报空指针的，所以说需要添加判断空值。 第二部是进行逻辑判断，因为是有大小的关系，如果需要寻找的整数，比数组【0】【0】的位置的数字都要小，就不需要在考虑了，因为这个数组最小的就是第【0】【0】元素。、 第三步就是我们暴力法开始运算，直接是一行一行的进行比较，只要相同就会跳出并且返回true，否则就是返回false。 时间复杂度：O(n*m) 空间复杂度：O(1)

二分法

可能他的意思并不是二分法，我看网上他们的计算方法也没有大看明白，我就说说自己会的这一种吧。 首先呢我们知道二维数组是有规律的，然后就是大小是从左至右依次增大，从上到下依次增大，于是我们找一个能够上下变化一致的角落，例如右上角或者是左下角，然后开始遍历，即可。

int col=array.length; if(col == 0){ return false; } int row=array[0].length; if(row ==0){ return false; } int start=0; int end=row-1; // 去的是右上角 while(start < col && end >= 0 ){ // 首先需要保证的是行不能够大于多少行的，然后是列的要大于等于零 if(array[start][end]==target ){ return true; }else if(array[start][end] > target){ --end; } else { ++start; } } return false; }

我们来稍微的解释一下这个代码。

首先找到这个二维数组的行数和列数，然后进行判断是否为空为了以外下面出现的空指针。然后找到右上角的坐标，然后开始使用while遍历，遍历的结束条件是到达边界。如果在这个过程中有合适的数，就选择true跳出循环，如果是没有合适的数则return false。 时间复杂度：O(m+n) 空间复杂度：O(1） 暂时话就这两种方法，方法可能会很多，等我第二遍乃至第三遍来梳理的时候来解决吧。