Leetcode题74、搜索二维矩阵（Python题解）Amazon面试题

77 阅读 0 评论 51 点赞

我是靠谱客的博主落寞香菇，最近开发中收集的这篇文章主要介绍Leetcode题74、搜索二维矩阵（Python题解）Amazon面试题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：

在这里插入图片描述

题目来源：力扣（LeetCode）

leetcode74.搜索二维矩阵

难度：中等

分析：
两个思路：
1、二分查找，关键地方在于求中点时行数用整除求，列数用取余求。
2、右上或左下角法，以右上角为例，观察右上角，右上角的值是行最大值和列最小值，可以用来做交界值。当目标值大于右上角值时，可以删除本行；当目标值小于右上角值时，可以删除本列。

解决方法：
1：二分查找

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]: return False
        row_num, col_num = len(matrix), len(matrix[0])
        left, right = 0, row_num * col_num - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[mid // col_num][mid % col_num] == target:
                return True
            elif matrix[mid // col_num][mid % col_num] > target:
                right = mid - 1
            else:
                left = mid + 1
        return False

2：右上角法

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