Leetcode题解剑指 Offer 04. 二维数组中的查找

PROBLEM

难度中等

MY ANSWER

相当于二叉搜索树。从右上角开始遍历，若值比target大则向左走，若小则向下走，无路可走时说明没有该整数，返回false。注意设置 j 初值时要考虑空矩阵的判断，否则过不了。时间复杂度O(n+m)，空间复杂度O(1)。

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

BETTER SOLUTION

思路相同，只不过从左下角开始遍历，好处是设置 i 初值时不需要判断空矩阵，耗时会少点。时间复杂度O(n+m)，空间复杂度O(1)。

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;
    }
};

SUMMARY

根据题目条件将矩阵抽象为二叉搜索树解决问题，解题时注意0值和边界判断。这题还尝试了用bfs解决，但时间过不了。