剑指 Offer - 04 二维数组中的查找

题目:

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

分析:

题目需要高效的函数，那肯定不能直接遍历数组了。
我们发现给定数组的特点是从左到右递增，从上到下递增，以左对角线为基准，左边的元素肯定是小于右边的元素。i为行数，j为列数，我们可以选择该对角线的两个边界点的值，也就是左下角和右下角的值为一个标志数。如果目标值大于该标志数，那么目标值一定在标志数所在列的右边，即j--；如果目标值小于该标志数，那么目标值一定在标志数所在行的左边，即i++；

代码实现:

    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            int i = matrix.length-1;
            int j = 0;
            while(i >= 0 && j < matrix[0].length){
                if(target > matrix[i][j])  j++;
                else if(target < matrix[i][j]) i--;
                else return true;
            }
            return false;
        }
    }

结果:

image.png