剑指offer 1.二维数组中的查找

深碍√TFBOYSˉ_ 2022-02-25 02:18 151阅读 0赞

时间限制：1秒 空间限制：32768K  
本题知识点： 查找  
题目描述  
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

方法一:传统遍历(较慢,只是能解决问题)

public class Solution { 
        public boolean Find(int target, int [][] array) { 
            boolean key = false;
            for (int i = 0; i < array.length; i++) { 
                for (int i1 = 0; i1 < array[i].length; i1++) { 
                    if(array[i][i1] == target) { 
                        key = true;
                        break;
                    }
                }
                if(key == true) { 
                    break;
                }
            }
          return key;
        }
    }

方法2:把每一行看成有序递增的数组，  
利用二分查找，  
通过遍历每一行得到答案，  
时间复杂度是nlogn

public class Solution { 
        public boolean Find(int [][] array,int target) { 
             
            for(int i=0;i<array.length;i++){ 
                int low=0;
                int high=array[i].length-1;
                while(low<=high){ 
                    int mid=low+(high - low)/2;
                    if(target>array[i][mid])
                        low=mid+1;
                    else if(target<array[i][mid])
                        high=mid-1;
                    else
                        return true;
                }
            }
            return false;
     
        }
    }

方法3:  
利用二维数组由上到下，由左到右递增的规律，  
那么选取右上角或者左下角的元素a\[row\]\[col\]与target进行比较，  
当target小于元素a\[row\]\[col\]时，那么target必定在元素a所在行的左边,  
即col–；  
当target大于元素a\[row\]\[col\]时，那么target必定在元素a所在列的下边,  
即row++；

public class Solution { 
        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;
     
        }
    }