题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
思路分析：
第一种思路
把每一行看成递增的数组，使用二分查找，遍历每一行得到结果，时间复杂度是nlogn public boolean Find(int target, int [][] array) { for(int i=0;i<array.length;i++){ int L=0,R=array[i].length-1; while(L<=R){ int mid=(L+R)/2; if(array[i][mid]<target){ L=mid+1; }else if(array[i][mid]>target){ R=mid-1; }else { return true; } } } return false; }
第二种思路：
这个二维数组是有序的，从左到右，从上到下是递增的，所以可以从该二维数组的左下角或者右下角的数开始比较，比如从左下角的数开始比较，如果要计较的数大于左下角的第一个数，则往右平移一位比较，若小于，则向上平移一位比较 public boolean Find(int [][] array,int target) { int row=0; int col=array[0].length-1; while(row<=array.length-1&&col>=0){ if(target==array[row][col]) return true; else if(target>array[row][col]) row++; else col–; } return false; }
最后修改于 2018-12-22
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。