[数据结构与算法]剑指offer学习笔记 | 二维数组的查找

题目

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

解决方法

将矩阵逆时针旋转45°，然后将其转化为图的形式，如下图所示：

?由于题目中给出的矩阵是已经排好序的，所以，我们可以看出原矩阵转化为图的形式以后，就成为了一棵二叉搜索树。对于树中的每一个元素，其左分支元素更小、右分支元素更大。

从根节点开始查找，遇到比target大的元素就向左，列号减一；遇到比target小的元素就向右，行号加一。

?代码实现

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i = matrix.size() - 1, j = 0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
};