leetcode刷题20——搜索矩阵系列

1.搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列；每行的第一个整数大于前一行的最后一个整数。

考察知识点：二分查找

思路：若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int left=0,right=m*n-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(matrix[mid/n][mid%n]==target)
                return true;
            else if(matrix[mid/n][mid%n]<target)
                left=mid+1;
            else
                right=mid-1;
        }
        return false;
    }
};
           

2.搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列；每列的元素从上到下升序排列。

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