力扣每日一题：74.搜索二维矩阵的三种解题方法

2022-05-16 92

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 力扣每日一题：74.搜索二维矩阵的三种解题方法

74. 搜索二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix/

难度：中等

题目：

编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

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

提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-104 <= matrix[i][j], target <= 104

示例：

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

分析：

凡是能通过暴力AC的题都不能算中等题...

这道题分别用暴力、贪心、二分完成

解题1.双层for循环：

class Solution:
    def searchMatrix(self, matrix, target):
        for i in matrix:
            for j in i:
                if j == target:
                    return True
                elif j > target:
                    return False
        return False

解题2.贪心算法：

class Solution:
    def searchMatrix(self, matrix, target):
        line = len(matrix) - 1
        row = len(matrix[0]) - 1
        i = j = 0
        while True:
            if matrix[i][j] == target:
                return True
            elif i < line and matrix[i + 1][j] <= target:
                i += 1
            elif j < row and matrix[i][j + 1] <= target:
                j += 1
            else:
                return False

解题3.二分查找：

class Solution:
    def searchMatrix(self, matrix, target):
        line = len(matrix)
        row = len(matrix[0])
        left = 0
        right = line * row
        while left < right:
            i, j = divmod((left + right) // 2, row)
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                left = i * row + j + 1
            else:
                right = i * row + j
        return False