各位题友大家好！今天是 @负雪明烛 坚持日更的第 65 天。今天力扣上的每日一题是「74. 搜索二维矩阵」。

解题思路

今天题目重点：每行数字都是升序的；每行的所有数字都比它上面的那一行大。

下面给了多种方法，效率越来越快。

方法一：遍历

该方法就是遍历查找每个位置，看 target 是否出现。这个方法也能通过本题。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == target:
                    return True
        return False

class Solution(object):
    def searchMatrix(self, matrix, target):
        return any(target in row for row in matrix)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        const int M = matrix.size(), N = matrix[0].size();
        int i = 0;
        while (i < M * N) {
            if (matrix[i / N][i % N] == target)
                return true;
            ++i;
        }
        return false;
    }
};

时间复杂度： $O(M * N)$
空间复杂度：$O(1)$

方法二：从左下角或者右上角开始查找

今天这个题目是 240. 搜索二维矩阵 II 的一个特例。建议也把 240 题做一下。

这个方法是利用了矩阵的性质，如果我们从右上角开始遍历：

如果要搜索的 target 比当前元素大，那么让行增加；
- 如果要搜索的 target 比当前元素小，那么让列增加；

class Solution(object):
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        row, col = 0, cols - 1
        while True:
            if row < rows and col >= 0:
                if matrix[row][col] == target:
                    return True
                elif matrix[row][col] < target:
                    row += 1
                else:
                    col -= 1
            else:
                return False

时间复杂度：$O(M + N)$
空间复杂度：$O(1)$

方法三：先寻找到所在行

该方法利用了题目给出的矩阵的性质：每行元素都是单调递增的，并且下一行的元素会比本行更大。所以：

如果 target 大于这一行的末尾元素，那么target 一定不在这一行中，只能出现在矩阵的下面的行中。

那么，假如 target < matrix[i][N - 1] 时，说明 target 可能在本行中出现，而且由于下面各行的元素都大于 matrix[i][N - 1] ，所以，不可能在下面的行中出现。此时，可以在本行中使用顺序查找，或者二分查找。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            if target > matrix[i][N - 1]:
                continue
            if target in matrix[i]:
                return True
        return False

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        const int M = matrix.size(), N = matrix[0].size();
        for (int i = 0; i < M; ++i) {
            if (target > matrix[i][N - 1])
                continue;
            auto it = find(matrix[i].begin(), matrix[i].end(), target);
            return it != matrix[i].end();
        }
        return false;
    }
};

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            if target > matrix[i][N - 1]:
                continue
            index = bisect.bisect_left(matrix[i], target)
            if matrix[i][index] == target:
                return True
        return False

时间复杂度：在行中遍历查找的时间复杂度是： $O(M + N)$；在行中进行二分查找的时间复杂度是 $O(M + log(N))$
空间复杂度：$O(1)$

方法四：两次二分查找

这个方法可以说是方法三的改进。在方法三种，我们是先遍历找到 target 在哪一行，然后在该行遍历或者二分查找的 target 。其实也可以先用二分找到 target 所在的行，然后在该行二分找到 target。

具体做法是，先找到 matrix[i][0] 小于 target 并且 matrix[i + 1][0] > target 的第 i 行，然后在该行内进行二分找到 target。

代码如下：

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        col0 = [row[0] for row in matrix]
        target_row = bisect.bisect_right(col0, target) - 1
        if target_row < 0:
            return False
        target_col = bisect.bisect_left(matrix[target_row], target)
        if target_col >= N:
            return False
        if matrix[target_row][target_col] == target:
            return True
        return False

时间复杂度： $O(log(M) + log(N))$
空间复杂度：$O(1)$

方法五：全局二分

这个方法，是我们在二维矩阵上进行二分查找，这其实相当于把二维矩阵当做一维来做，要求每一行的最后一个元素小于下一行的第一个元素。

根据 mid 求出在二维矩阵中的具体位置，然后判断 left 和 right 的移动方式。整体做法和一维数组的二分没有区别。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        left, right = 0, M * N - 1
        while left <= right:
            mid = left + (right - left) // 2
            cur = matrix[mid // N][mid % N]
            if cur == target:
                return True
            elif cur < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

时间复杂度： $O(log(M * N))$
空间复杂度：$O(1)$
方法六：reshape成一维数组

如果用python刷题，在leetcode中是支持使用 numpy 的，可以把 matrix成一维有序的数组，然后按照一维数组去操作查找。

import numpy as np
class Solution(object):
    def searchMatrix(self, matrix, target):
        matrix = np.reshape(matrix, [1, -1])
        return target in matrix

import numpy as np
class Solution(object):
    def searchMatrix(self, matrix, target):
        matrix = np.reshape(matrix, [1, -1]).tolist()[0]
        index = bisect.bisect_left(matrix, target)
        if index < 0 or index >= len(matrix):
            return False
        return matrix[index] == target

时间复杂度： $O(MN + log(MN))$
空间复杂度：$O(M*N)$

刷题心得

今天提供了很多解法，希望能帮助你打开思路。
- 做完本题之后，去做一下 240. 搜索二维矩阵 II。

参考资料：
负雪明烛
 力扣官方题解

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】74. 搜索二维矩阵