题目描述

在一个 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。

限制：

0 <= n <= 1000

0 <= m <= 1000

思路

其实最简单的思路就是一个一个找呗，那还能找不到，但是这样的话算法就显得很笨，也没有充分的利用题目中说的每行按照从左到右递增的顺序排序这一信息。就不算是一个完美的结题。

所以我们可以采用下面这种方法：

因为这个二维数组有着顺序关系，所以遍历肯定是不明智的选择，我们的做法是从右上角开始，如果目标比右上角大那就减去一行，如果小，那就减去一列。通过这样的方式去检索是否有目标数字。难点在于求这个二维数组的行数和列数。

• vector数组
  vector<vector< int >> matrix；
  解释：这样写是表示二维数组，因为vector容器表示的是一维数组，所以vector<vector>这种形式的数组是二维数组，<>里面是数组的类型
  行数：matrix.size();
  列数：matrix[0].size();

• 二维数组：
  int matrix[ ][ ];
  a = sizeof(matrix[0][0]);//一个元素占得空间
  b= sizeof(matrix[0]);//一行所占的空间
  c= sizeof(matrix);//整个数组占得空间
  行数： sizeof(matrix) /sizeof(matrix[0])
  列数：sizeof(matrix[0]) / sizeof(matrix[0][0])

代码

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
       bool found = false;
        if(matrix.size()==0||matrix[0].size()==0) return false;
        int row = matrix.size();   //行数
        int cloumn = matrix[0].size();  //列数
        if(row>0&&cloumn>0){
                int row1 = 0;
                int cloumn1 = cloumn-1;
                while(row1<row && cloumn1>=0){
                    if(matrix[row1][cloumn1]==target){
                        found = true;
                        break;
                    }
                    else if(matrix[row1][cloumn1]>target)
                    --cloumn1;
                    else
                    ++row1;
                }

        }
        return found;

    }
};