题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
方法一：暴力破解。直接遍历一遍数组，即可判断目标target是否存在。时间复杂度O(n^2)(最坏的情况下，数组中的元素都需要遍历一次），空间复杂度为o(1).
public static boolean Find1(int target, int [][] array) {int length1=array[0].length;for(int i=0;i<length1;i++){for(int j=0;j<length1;j++){if(array[i][j]==target)return true;}}return false;}
方法二：利用该二维数组的性质
- 每一行都按照从左到右递增的顺序排序
- 每一列都按照从上到下递增的顺序排序。
也就是说，对于右上角的值m，m是该行最大的数，是该列最小的数。每次将m与target进行比较：
- 当m>target，由于m是该列最小的数了，想要更小，只能考虑列，取值左移一位
- 当m<target，由于m是该行最大的数，想要更大，只考虑行了，取值下移一位
- 当找到了m==target,返回true
用某行最小或某列最大与 target 比较，每次可剔除一整行或一整列
/*** 选取右上角的* @param target* @param array* @return*/public static boolean Find2(int target, int [][] array) {int i=0;int j=array.length-1;while(i<=array.length-1 && j>=0){if(array[i][j]>target){j--;}else if(array[i][j]<target){i++;}elsereturn true;}return false;}
选取左下角：
/*** 选取左下角*/public static boolean Find3(int target, int [][] array) {if(array[0].length==0){return false;}//这是该行最小的数，该列最大的数int i=array.length-1;int j=0;while(i>=0 && j<=array.length-1){//当大于target的时候，想要最小，只能考虑行，行上移一位if(array[i][j]>target){i--;}//当小于target,想要更大，只能考虑列，列右移一位else if(array[i][j]<target){j++;}elsereturn true;}return false;}
时间复杂度o(行高+列宽），空间复杂度o(1)。
要注意：不能选取左上角和与下角的数字。还要注意判断传入的数组的长度，在测试用例中，还有可能传入空数组。