题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//解决思路: //如数组样式如下: // 1 2 3 4 // 2 3 4 5 // 3 4 5 6 //正常查找的过程,本质就是排除的过程,如果双循环查找,本质是一次排除一个,效率过低 //根据题面要求,我们可以采取从右上角(或左下角)进行比较(想想为什么?),这样可以做到一次排除一行或者一列
1、忽略时间空间复杂度，直接遍历，暴力解法
public class Solution { public boolean Find(int target, int [][] array) { for (int[] ints : array) { for (int anInt : ints) { if(anInt==target) return true; } } return false; } }
2、优化解法，考虑时间和空间复杂度
看到查找应该，就是想尽办法去排除。
查找的过程中你排除的越多，你的算法也就越快。
根据题面要求,我们可以采取从右上角(或左下角)进行比较(想想为什么?),这样可以做到一次排除一行或者一列
if(array==null) return false; int i = 0,//i：指向每一行最小的值 j=array[0].length-1;//j：指向每一行最大的值 while (i < array.length && j >=0 ){ //此时array[i][j] 一定这一行最大的 if(target < array[i][j]){ j--;//如果比这一行的最大值小，指向这一行最大值的指针j就j-1,移动下一个元素 //如果查找的数大于这个最大值，就说明肯定是在这一列，那么就i++就可以继续找这一列了 }else if (target > array[i][j]){ i++; //查找成功返回true }else{ return true; } } return false;
