leetcode刷题 74.搜索二维矩阵

leetcode刷题 74.搜索二维矩阵

题目分析
这是一道简单的查找二维矩阵的题目，所以解决这题有一个最简单的解法就是遍历二维数组即可；但是我们应该注意到题目中的每行整数从左到右是按升序排列的，第一个整数大于前一行的最后一个整数，介于此，我们可以想到使用二分查找。

解法1：

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target)
    {
        for(auto i:matrix)
        {
            for(auto j:i)
            {
                if(j==target)
                    return true;
            }
        }
        return false;
    }
};

解法二：

class Solution {
public:
    int row, col;
    pair getIndex(int n) {
        return {n/col, n%col};				//通过这个方式，将一维数组地址转换为二维数组坐标，也是本解法的精华
    }
    bool searchMatrix(vector>& matrix, int target) {
        row = matrix.size(), col = matrix[0].size();
        int left = 0, right = row*col - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            auto [i, j] = getIndex(mid);
            if(matrix[i][j] == target)
                return true;
            else if(matrix[i][j] > target)
                right = mid-1;
            else if(matrix[i][j] < target)
                left = mid+1;
        }
        return false;
    }
};

作者：AC_OIer
链接：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-fe-l0pq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。