二维数组中的查找【Java版】
二维数组中的查找
http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
public class Solution { public boolean Find(int target, int [][] array) { if(array.length==0 || array[0].length==0)return false; //尽量都写成左闭右闭区间的风格,在一开始就减一,上下界都是能够达到的值 int row = array.length -1; int col = array[0].length -1; //这里从右上开始,左下也可以。 //(不能从左上开始,不然不知道移动的方向。更不能从任意位置开始) int i = row; int j =0; while(i>=0 && j<=col){//范围用>=和<=,这样配合左闭右闭区间 if(array[i][j]>target)--i;//【每次判断都能剔除一整行或一整列】 else if(array[i][j]<target)++j;//这里的else if 不能用else,因为上面的语句可能会影响array[i][j]的值(改变了i的值) else return true;//将==放在最后,因为这个情况的概率最小,这样效率更高 } return false; } } //时间复杂度:O(col+row) //空间复杂度:O(1)
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》