书籍在行列都排好序的矩阵中找数(8)0626

题目：

给定一个有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。

解答：

符合要求的解法比较巧妙且易于理解。

可以用以下步骤解决：

1、从矩阵最右上角的数开始寻找(row = 0,col=M - 1)。

2、比较当前数matrix[row][col]与K的关系：

 如果与K相等，说明已找到，直接返回true。

如果比K大，因为矩阵每一列都已排好序，所以在当前数所在的列中，处于当前数下方的数都会比K大，则没有必要继续在第col列上寻找，令col=col-1,重复步骤2.

如果比K小，因为矩阵每一行都已排好序，所以在当前数所在的行中，处于当前数左方的数都会比K小，则没有必要继续在第row行上寻找，令row = row + 1，重复步骤2。

public boolean isContains(int[][] matrix,int K){int row = 0;int col = matrix[0].length - 1;while(row <  matrix.length && col > -1){if(matrix[row][col] == K){return true;}else if(matrix[row][col] > K){col--;}else{row++;}}return false;
}