剑指offer-二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

时间限制：1秒空间限制：32768K 热度指数：29783

我的方法：从数组每行第一个元素开始判断是否小于或等于目标值，若是就遍历该行

难点备注：二维数组判断的条件

 1 public class Solution {
 2     public boolean Find(int target, int [][] array) {
 3         
 4         boolean flag=false;
 5         
 6         if(array==null||array.length==0||(array.length==1&&array[0].length==0)){
 7             return flag;
 8         }
 9         
10         for(int i=0;!flag&i<array.length;i++){
11             if(target>=array[i][0]){
12                 for(int j=0;j<array[i].length;j++){
13                     if(array[i][j]==target){
14                             flag=true;break;
15                     }
16                 }
17             }
18         }
19         
20         return flag;        
21     }
22 }

优秀解法：

/* 思路矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时。右移 要查找数字比左下角数字小时，上移*/

 1 链接：https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
 2 来源：牛客网
 3 
 4 class Solution { 
 5  public:
 6      bool Find(vector<vector<int> > array,int target) {
 7          int rowCount = array.size();
 8          int colCount = array[0].size();
 9          int i,j;
10          for(i=rowCount-1,j=0;i>=0&&j<colCount;)
11          {
12              if(target == array[i][j])
13                  return true;
14              if(target < array[i][j])
15              {
16                  i--;
17                  continue;
18              }
19              if(target > array[i][j])
20              {
21                  j++;
22                  continue;
23              }
24          }
25          return false;
26      }
27  };

链接：https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
来源：牛客网

两种思路

一种是：

把每一行看成有序递增的数组，

利用二分查找，

通过遍历每一行得到答案，

时间复杂度是nlogn

 1 public class Solution {
 2     public boolean Find(int [][] array,int target) {
 3          
 4         for(int i=0;i<array.length;i++){
 5             int low=0;
 6             int high=array[i].length-1;
 7             while(low<=high){
 8                 int mid=(low+high)/2;
 9                 if(target>array[i][mid])
10                     low=mid+1;
11                 else if(target<array[i][mid])
12                     high=mid-1;
13                 else
14                     return true;
15             }
16         }
17         return false;
18  
19     }
20 }

另外一种思路是：

利用二维数组由上到下，由左到右递增的规律，

那么选取右上角或者左下角的元素a[row][col]与target进行比较，

当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,

即col--；

当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,

即row++；

 1 public class Solution {
 2     public boolean Find(int [][] array,int target) {
 3         int row=0;
 4         int col=array[0].length-1;
 5         while(row<=array.length-1&&col>=0){
 6             if(target==array[row][col])
 7                 return true;
 8             else if(target>array[row][col])
 9                 row++;
10             else
11                 col--;
12         }
13         return false;
14  
15     }
16 }