学步园

题目如下:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

分析如下:

进行了很多尝试，
第一种解法：
一开始，找到最中间的元素mid，以它为中心，延伸穿过它的行和列，容易将矩形划分成四块，对这四块进行分析，发现如果target>mid，那么mid左上角的矩形一定不含target，下一次搜索可以抛弃。如果target<mid，那么mid右下角的矩形一定不含target，下一次搜索可以抛弃，这样递归进行。这个想法比较自然，但是注意的是，非常容易写成死循环。具体见代码一。这个代码的时间复杂度，需要用Master Theorem计算一下，leetcode官网有详细解释，就不搬运了，计算结果是O(N的lg3次方，假设是N*N矩形。)
第二种解法：
然后，看了看官网，找到一个不错解法，从右上到左下，依次检查当前元素cur，如果target>cur，那么cur所在的列都不用检查了，列向左推进一步。如果target<cur，那么cur所在的行都不用检查了，行向下推荐一步。如果target==cur，返回cur。这个过程是个从右上走到左下的过程。最多走N+M步（N,M是边长），所以，时间复杂度为O(N+M)。具体见代码二。具体过程如下图:

我的代码：

//代码一
//递归，矩阵分成四块，每次丢弃一块。
class Solution {
public:
    bool searchMatrix_(vector<vector<int> > &matrix,int row_start,int row_end, int col_start, int col_end,int target){
        if(row_start>row_end||col_start>col_end)
            return false;
        if(row_start==row_end&&col_start==col_end&&matrix[row_start][col_start]==target)
            return true;
        if(row_start==row_end&&col_start==col_end&&matrix[row_start][col_start]!=target)
            return false;
        int row_mid=row_start+(row_end-row_start)/2;
        int col_mid=col_start+(col_end-col_start)/2;
        int val_mid=matrix[row_mid][col_mid];
        if(target==val_mid)
            return true;
        if(target>val_mid){
            if (searchMatrix_(matrix,row_mid+1,row_end,col_mid+1,col_end,target)
              ||searchMatrix_(matrix,row_start,row_mid,col_mid+1,col_end,target)
              ||searchMatrix_(matrix,row_mid+1,row_end,col_start,col_mid,target))
//注意这里很容易造成死循环，右下角那块非常容易造成死循环。如果写为“searchMatrix_(matrix,row_mid,row_end,col_mid,col_end,target)||...”就会死循环。测试案例,当最后只剩四个元素时，mid正好在左上角，如果这么写，就死循环。
                return true;
        }
        if(target<val_mid){
            if(searchMatrix_(matrix,row_start,row_mid,col_start,col_mid,target)
             ||searchMatrix_(matrix,row_start,row_mid,col_mid+1,col_end,target)
             ||searchMatrix_(matrix,row_mid+1,row_end,col_start,col_mid,target))
                return true;
        };
        return false;
    }
    
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if(matrix.empty())
            return false;
        int m=(int)matrix.size();
        int n=(int)matrix[0].size();
        return searchMatrix_(matrix, 0,m-1,0,n-1,target);
    }
};

//代码二
//从右上到左下依次走
class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if(matrix.empty())
            return false;
        int row_num=(int)matrix.size();
        int col_num=(int)matrix[0].size();
        int row=0;
        int col=col_num-1;
        if(target>matrix[row_num-1][col_num-1]||target<matrix[0][0])
            return false;
        while(row<row_num&&col>=0){
            if(target>matrix[row][col])
                row++;
            else if(target<matrix[row][col])
                col--;
            else
                return true;
        }
        return false;
    }
};

小结:

(1) 矩形是从左下到右上递增，所以比较倾向于从左上到右下找元素。这道题说明，从右上到左下找元素，才能借助行向右增长，列向下增长的条件尽快地搜索。

参考资料:

(1) http://oj.leetcode.com/problems/search-a-2d-matrix/