剑指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。

思路分析

对于题设中的矩阵，因为每一行非递减，每一列非递减，构成指教的一行与一列是非递减的，如第0行和第m-1列，第一行的前三个元素和和第一列的后四个元素

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

---

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

因此针对这样的一个非递减的直角,从右上角开始,比较角的值与目标的大小,如果大于目标值,则说明目标在角的下部分,如果大于说明再左侧。如目标为18,18>15,则15所在的行全部都小于18,所以目标18只可能在15下面的部分.

代码实现

class Solution
{
public:
    bool findNumberIn2DArray(vector<vector<int>> &matrix, int target)
    {
        //计算二维数组的长度
        int n = matrix.size();
        //如果数组为空,返回false
        if( n == 0){
            return false;
        }
        // 在数组不为空的前提下,计算数组中一维数组的长度
        // 如果不先判空,而是先定义m,当数组为空时,会出现matrix[0]空指针异常
        //因为matrix数组没有索引0对应的值
        int m = matrix[0].size();
        // 从右上角开始
        // 定义上边界
        int top = 0;
        // 定义右边界
        int right = m - 1;
        // 一直遍历到左下角
        while (top < n && right >=0)
        {
            // 如果当前的角的值等于target,搜索成功,返回
            if (matrix[top][right] == target){
                return true;
            }
            // 如果当前的角的值>target
            // 说明目标在左侧,右边界左移
            else if (matrix[top][right] > target){
                right --;
            }
            // 如果当前的角的值>target
            // / 说明目标在下侧,上边界下移
            else{
                top ++;
            }
        }
        // 遍历完了整个数组，说明没找到，返回flase
        return false;
    }
};

通过截图