leetcode 240.搜索二维矩阵II 分治思想

题目描述

搜索二维矩阵II:原题链接

思路

这道题的关键在于得找到特殊位置的起始点，从该起始点，可以分治地去查找待查找地点。
主对角线上左上角和右下角不符合条件，因为

• 左上角的点，其周围的点都比它大，没法找到合适的查找路径
• 右下角的点，其周围的点都比它小，没法找到合适的查找路径

次对角线上左下角和右上角的点更合适，因为

• 左下角的点：往上比它小，往右比它大
• 右上角的点：往左比它小，往下比它大

因此，选择左下角或右上角的点都合适。

代码

选择右上角的点为起点：

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

选择左下角的点为起点：

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