搜索二维矩阵 II

题目

搜索二维矩阵 II

思路

看到这个题的时候我第一时间想到二分
逐行二分遍历矩阵图

AC代码

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


我过了之后去看了题解 另一种更快的解法双指针

双指针

左下角是一行中最小,一列中最大
如果大于则往上跑 小于则往右跑

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)return false;//注意空的情况
        int a = 0;
        int b = matrix[0].size() - 1;
        while(b >= 0 && a < matrix.size())
        {
            if(matrix[a][b] == target)
                return true;
            else if(matrix[a][b] > target)b--;
            else a++;
        }
        return false;
    }
};


本质上还是二分吧!

Last modification:April 4th, 2020 at 12:59 pm
如果觉得我的文章对你有用,请随意赞赏