leetcode_74 搜索二维矩阵

1. 题意

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。

• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；

否则，返回 false 。

2. 题解

2.1 暴力

逐个判断即可;

时间复杂度$O(mn)$

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

2.2 逐行二分

由于一行的数是有序的，因此可以不用完全遍历。

而且二分查找target。

时间复杂度$O(m\log n)$

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (0 == m)
            return false;
        
        for (int i = 0;i < m; ++i) {
            auto it = lower_bound( matrix[i].begin(), matrix[i].end(), target);
            if ( it != matrix[i].end() && *it == target)
                return true;
        }

        return false;
    }
};

2.3 整体二分

由于$r$行的最后一个元素是小于$r+1$行的第一个元素。

我们可以将这个二维数组给看成一个有序的一维数组。

用下标$k$表示原来数组$matrix[k/n][k\%n]$这个元素，

在$[0,mn)$这个新下标间进行二分。

时间复杂度$O(\log mn)=O(\log m+\log n)$

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

        int l = 0;
        int r = m * n - 1;


        while ( l <= r) {
            int mid = ((r - l) >> 1) + l;

            int v = matrix[mid / n][mid % n];

            if ( v == target)
                return true;
            if ( v > target)
                r = mid - 1;
            else 
                l = mid + 1;
        }



        return false;
    }
};

2.4 两次二分

我们可以二分查找最后一列，找到第一个不小于$target$所在的行。

在对行进行二分，查找最终的$target$值。

时间复杂度$O(\log m+\log n)$

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

        
        int l;
        int r;

        l = 0;
        r = m;
        // log m
        while ( l < r) {
            int mid = ((r - l) >> 1) + l;

            int v = matrix[mid][n - 1];
            if ( v == target)
                return true;
            
            if ( v > target)
                r = mid;
            else
                l = mid + 1;
        }

        if ( r >= m )
            return false;

        int rows = r;

        //cout << rows << endl;
        l = 0;
        r = n;

        while ( l < r) {
            int mid = ((r - l) >> 1) + l;

            //cout << mid << ": " << matrix[rows][mid] << endl;

            int v = matrix[rows][mid];
            if ( v == target)
                return true;

            if ( v < target)
                l = mid + 1;
            else 
                r = mid;
        }

        return false;
    }
};

2.5 二叉搜索树

这个想法来自三叶姐，宫水三叶。

把这样的二维数组想看成以右上角为根节点的二叉搜索树。

当前节点的左边节点必然小于当前节点，

当前节点的下边节点必然大于当前节点。

我们从根开始，如果当前节点大于target，就向左走；

如果当前节点小于target，就向下走。

重复上面的过程，直到超过边界或者找到target。

时间复杂度$O(m+n)$

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

        int x = 0;
        int y = n - 1;

        while (x < m && y >= 0) {
            int v = matrix[x][y];

            if (v == target)
                return true;
            
            if ( v > target)
                y--;
            else 
                x++;
        }
        

        return false;
    }
};

参考

三叶
leetcode