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

简介: 力扣每日一题: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




相关文章
|
4月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
人工智能 自然语言处理 程序员
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
欢迎来到工程师令狐小哥的频道。本文介绍如何利用AI工具高效刷LeetCode,通过通义灵码插件在IntelliJ IDEA中实现代码生成、优化、单元测试等功能,提升编程学习效率。
92 1
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
17 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
25 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
20 0
|
2月前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
18 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
4月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
4月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
4月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组