240. 搜索二维矩阵 II

一 题目:

二 思路:

• 本题具有非常强的规律性,
  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
• 假设我们现在遍历的索引是其中的某个点matrix[x][y],那么我们就知道该怎么走了
  • 如果target等于matrix[x][y],就代表找到了
  • 如果target大于matrix[x][y],我们要向下走去找
  • 如果target小于matrix[x][y],我们要向左走去找
• 另外为了避免往回找,我们要找到走向无二义性的极值点
  • 比如右上角的点,只需要向左或者向下就可以了,向左一定变小,向you下就一定变大
  • 再比如左下角的点,向上一定变小,向右一定变大
  • 左上角右下角的点不能选,因为其向右向下都变大,右下角的点向上向左均变小

三 代码:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int x=0,xMax=matrix.length-1,y=matrix[0].length-1,yMin=0;

        while (x<=xMax&&y>=yMin){
            if (matrix[x][y]==target){
                return true;
            }

            if (matrix[x][y]>target){
                y--;
            }else{
                x++;
            }
        }

        return false;
    }
}