力扣网 | 算法面试题汇总 | 开始之前 | 搜索二维矩阵 II

文章目录

• 题目
• 解析

题目

算法面试题汇总 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

解析

暴力

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

剪枝

初始左下角指针（row = matrix.size()-1,col=0）：

• 如果等于target，返回true；
• 如果小于target，col+=1(因为每行从左到右，从小到大)；
• 如果大于target，row-=1(因为每列从下到上，从大到小)；

简而言之，每个指针，所在列上面的会比它小，下面会比它大；所在行左边比它小，右边比它大；

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

二分法

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

        }
        return false;
    }
};
/*
作者：zrita
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/c-xian-xing-cha-zhao-er-fen-z-by-zrita/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/