没有思路就是莽:
public class Solution { public boolean Find(int num, int [][] array) { if(array.length==0) return false; //if(num<array[0][0]||num>array[array.length-1][array[0].length-1]) return false;加上这句就错了 for(int i=0;i<array.length;i++){ for(int j=0;j<array[0].length;j++){ if(array[i][j]==num){ return true; } } } return false; } }
思路1:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是nlogn
public class Solution { public boolean Find(int target,int [][] array) { for(int i=0;i<array.length;i++){ int low=0; int high=array[i].length-1; while(low<=high){ int mid=(low+high)/2; if(target>array[i][mid]) low=mid+1; else if(target<array[i][mid]) high=mid-1; else return true; } } return false; } }
思路2:从左下角元素往上查找,右边元素是比这个元素大,上边是的元素比这个元素小。于是,target比这个元素小就往上找,比这个元素大就往右找。如果出了边界,则说明二维数组中不存在target元素。
public class Solution { public boolean Find(int target, int [][] array) { int rows = array.length; int cols = array[0].length; int i=rows-1,j=0; while(i>=0 && j<cols){ if(target<array[i][j]) i--; else if(target>array[i][j]) j++; else return true; } return false; }