欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数组、二分搜索二维矩阵

程序员文章站 2024-01-28 12:25:28
1、题目描述https://leetcode-cn.com/problems/search-a-2d-matrix/编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数(变成了240题的特例)。通用模板就看LeetCode240:搜索二维矩阵IIhttps://blog.csdn.net/IOT_victor/article/details/104642324本题解法在.....

1、题目描述

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

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。

该矩阵具有如下特性:

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数(变成了240题的特例)

数组、二分搜索二维矩阵

通用模板就看 LeetCode240:搜索二维矩阵II https://blog.csdn.net/IOT_victor/article/details/104642324

本题解法在240基础上加了优化

2、代码详解

法一:缩小领域法

因为每一行递增,每一列递增。所以我们可以从右上角往左下角找或者从左下角往右上角找。

每次比较可以排除一行或者一列,时间复杂度为O(m+n)

class Solution(object):
    def searchMatrix(self, matrix, target):
        # m * n
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        # 左下角(必须这么设置!左下角:最后一行的最小值)从下向上
        row = m - 1
        col = 0
        while row >= 0 and col <= n-1:
            # 优化:当前行的最大值 < target
            if matrix[row][n-1] < target:
                return False
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else:
                return True
        return False

        # # 右上角(必须这么设置!右上角:第一行的最大值)从上向下
        # row = 0  # 行
        # col = n - 1  # 列
        # while row <= m-1 and col >= 0:
        #     # 优化:当前行的最小值 > target
        #     if matrix[row][0] > target:
        #         return False
        #     if matrix[row][col] > target:  # 在本行中
        #         col -= 1
        #     elif matrix[row][col] < target:  # 加行
        #         row += 1
        #     else:
        #         return True
        # return False

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
s = Solution()
print(s.searchMatrix(matrix, target))

法二:标准的二分查找模板

将二维矩阵拖为一维矩阵,然后就是一个有序的一维数组了,利用二分查找就行

本文地址:https://blog.csdn.net/IOT_victor/article/details/107081728