描述

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

思路1：暴力循环

双重遍历，查找矩阵中每一个元素，代码比较简单不贴了。时间复杂度O(nm)

思路2：双指针移动

可以将数组旋转45度观看，类似二叉搜索树

因此可以从左下角（或者右上角）开始查找，小于目标值则往上搜索，大于目标值则往右搜索。

public class Solution {
    public boolean Find(int target, int [][] matrix) {
        if (matrix.length == 0) {
            return false;
        }
        //从左下角开始搜索
        int i = 0; //第i列
        int j = matrix.length - 1; //第j行
        while (j >= 0 && i < matrix[0].length) {
            int value = matrix[j][i];
            if (value < target) {
                i++;
            } else if (value > target) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}