[数据结构与算法]【剑指offor】面试题4：二维数组中的查找

题目描述

在一个 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这种形式的数组是二维数组，<>里面是数组的类型
  行数：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;

    }
};