【题目】

　　给定一个N×M的整型矩阵matrix和一个整数K，matrix的每一行和每一列都是排好序的。实现一个函数，判断K是否在matrix中

 　  例如，   0   1   2   5

                 2   3   4   7

                 4   4   4   8

                 5   7   7   9

　　　　如果K为7，返回true；如果K为6，返回false；

【要求】

　　时间复杂度为O(N+M)，额外空间复杂度为O(1)

 

my:

1     public boolean isContains(int[][] matrix, int k) 2     { 3         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) 4         { 5             return false; 6         } 7  8         int col = matrix[0].length - 1; 9         for(int i = 0; i < matrix.length; i++)10         {11             if(matrix[i][col] >= k)12             {13                 for(int j = col; j > -1; j--)14                 {15                     if(matrix[i][j] == k)16                     {17                         return true;18                     }19                     else if(matrix[i][j] < k)20                     {21                         break;22                     }23                 }24             }25         }26         return false;27     }

 时间复杂度为O(N*M)，空间复杂度为O(1)，因为每一行每一列都是排好序的，所以如果遍历到某一行时发现其元素都比k大，说明k不在矩阵中，之后的所有行都不用访问了，因为当某一行的元素都比k大时，下面行的元素一定都比k大，所以如果在遍历的过程中某一行中的元素全部被遍历仍然没有找到k时，就可以判定结果了。

 

左老师：

1     public boolean isContains(int[][] matrix, int k) 2     {     3         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) 4         { 5             return false; 6         } 7  8         int row = 0; 9         int col = matrix[0].length - 1;10         while(row < matrix.length && col > -1)11         {12             if(matrix[row][col] == k)13             {14                 return true;15             }16             else if(matrix[row][col] > k)17             {18                 col--;19             }20             else21             {22                 row++;23             }24         }25         return false;26     }

 时间复杂度为：O(N+M)，空间复杂度为：O(1)

 

来源：左程云老师《程序员代码面试指南》