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




相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
2月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
2月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
2月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
40 6
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
25 4
|
2月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
20 0
【Leetcode刷题Python】73. 矩阵置零
|
2月前
|
算法 Python
【Leetcode刷题Python】74. 搜索二维矩阵
两种解决LeetCode "搜索二维矩阵" 问题的方法的Python实现。第一种方法是从二维矩阵的右上角开始线性搜索,通过比较当前元素与目标值来决定搜索方向。第二种方法是将二维矩阵视为一维数组进行二分查找,通过计算中间元素的行列索引来更新搜索区间。两种方法都旨在高效地判断目标值是否存在于给定的有序二维矩阵中。
25 0
|
2月前
|
算法 索引 Python
【Leetcode刷题Python】33. 搜索旋转排序数组
解决LeetCode "搜索旋转排序数组" 问题的Python实现代码。代码使用了二分查找算法,首先检查目标值是否存在于数组中,然后通过比较数组中间值与数组首尾值来确定应该在数组的哪一半继续搜索,直到找到目标值或搜索范围为空。如果找到目标值,返回其索引;如果搜索结束仍未找到,返回 -1。
13 0