剑指offer04(中等)：二维数组中的查找

题目

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

示例：

 matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

代码

方案1：暴力破解

直接遍历二维数组。

存在元素=target，返回true，否则，返回false。

显然，暴力破解并没有用到题目给数组的限制条件：

每一行都按照从左到右递增的顺序排序

每一列都按照从上到下递增的顺序排序

正因为如此，恰好验证了暴力破解不是该题目高效的算法。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int height = matrix.length;
        if(height==0){
            return false;
        }
        int width = matrix[0].length;

        for(int i=0;i<height;i++){
            for(int j=0;j<width;j++){
                if(matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;

    }
}

方案2：算法优化

抓有特征的元素。

在这里是左下角元素和右上角元素：

左下角元素：所在行元素，均比它大；所在列元素，均比它小。

右上角元素：所在行元素，均比它小；所在列元素，均比它大。

选择一个有特征的元素即可。

将左下角元素作为flag(标志元素)：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int height = matrix.length;
        if(height==0){
            return false;
        }

        int width = matrix[0].length;

        int i=height-1,j=0;

        while (i>=0 && j<=width-1){
            int flag = matrix[i][j];
            if(target<flag){
                i--;
            }else if(target>flag){
                j++;
            }else {
                return true;
            }
        }

        return false;
    }
}

将右上角元素作为flag(标志元素)：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int height = matrix.length;
        if(height==0){
            return false;
        }

        int width = matrix[0].length;

        int i=0,j=width-1;

        while (i<=height-1 && j>=0){
            int flag = matrix[i][j];
            if(target<flag){
                j--;
            }else if(target>flag){
                i++;
            }else {
                return true;
            }
        }

        return false;

    }
}

随笔

复杂度分析

方案1：

时间复杂度：O(n * m)，最多循环 n * m 次。

空间复杂度：几个变量使用常数大小的额外空间。

方案2：

时间复杂度：O(n + m)，最多循环 n + m 次。

空间复杂度：几个变量使用常数大小的额外空间。