首页 > 其他分享 >LeetCode 热题 100 之 240. 搜索二维矩阵 II

LeetCode 热题 100 之 240. 搜索二维矩阵 II

时间:2023-08-08 21:44:47浏览次数:42  
标签:遍历 return matrix int List II 240 热题 target

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例一

image

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true

示例二:

image

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false

提示:

m == matrix.length

n == matrix[i].length

1 <= n, m <= 300

-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

思路:

思路一:
暴力解法,直接两层循环遍历,可行原因,m,n较小,O(mn)的时间复杂度并不大。

思路二:
对每行进行遍历,采用二分法进行行遍历(行有序),注意遍历前可以特判,若行首比目标还大,说明此后的所有行都会比目标值大,结束遍历返回false,若行尾比目标值还小说明当前行肯定都比目标小,不需要遍历改行,直接contine,若特殊情况都不满足,则对改行进行二分查找。

思路三:
巧妙的从右上角进行遍历,若当前值大,则往左移动一位,若当前值小,则往下移动一位。

代码

思路一

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==target:
                    return True
        return False

思路二

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def serachdata(matrixline:List[int],target:int) -> bool:
            n = len(matrixline)
            l = 0
            r = n-1

            while(l<=r):
                mid = (l+r)//2
                if(matrixline[mid]>target):
                    r =mid-1
                elif matrixline[mid]<target:
                    l = mid+1
                elif matrixline[mid]==target:
                    return True
            return False
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            if(matrix[i][-1]<target):
                continue
            if matrix[i][0]>target:
                break
            if serachdata(matrix[i],target):
                return True
        return False

思路三

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

标签:遍历,return,matrix,int,List,II,240,热题,target
From: https://www.cnblogs.com/anamzingclown/p/17615462.html

相关文章

  • win10 iis - 开启iis且配置站点后,访问静态页面空白 - 解决
     勾选这三个即可 ......
  • 内存溢出后重启IIS后,附加到进程调试 ,找不到w3wp.exe进程。
    打开IIS,右键浏览一下。这个时候附加到进程调试里的选项就有了!本文来自博客园,作者:小二↑上酒,转载请注明原文链接:https://www.cnblogs.com/qh1688/p/7383925.html......
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III(中等)
    题目:解法一:classSolution{public:voidtraversal(TreeNode*cur,vector<vector<int>>&result,intdepth){if(cur==nullptr)return;if(result.size()==depth)result.push_back(vector<int>());result[depth].pu......
  • Windows server 2003怎么安装iisWindows server 2003安装IIS教程
    Windows2008系统服务器安装IIS之前已经分享过了,和Windows2003完全不同,今天我将详细地和你分享Windowsserver2003卸载和安装IIS的步骤方法,希望可以帮助到你~1、首先进入服务器,确定下服务器是否有安装IIS,有安装IIS,需要重装的,可以先将IIS卸载。2、卸载比安装更简单些,点击开始——......
  • [国家集训队] Tree II 题解报告
    [国家集训队]TreeII一道·真·板子·题就是练习LCT懒标记的题目除了翻转标记以外还要维护乘法标记和加法标记注意加法标记和乘法标记的维护!!!加法标记因为splay的区间大小不是固定的,所以我们要维护size,并且子树的sum要加上size乘上标记其他的就只用直接加上即可voidpusha......
  • SQLServer 2000 服务不能启动的多种解决办法43.240.156.X
    一、在服务器上以管理员帐户登录操作系统。43.240.156.2二、尝试通过操作系统中的服务来启动SQLServer服务:43.240.156.3  1、在“我的电脑”上点击右键,选择“管理”菜单。43.240.156.4  2、在“计算机管理”程序中,依次展开服务和应用程序->服务。43.240.156.5  3、......
  • 代码随想录算法训练营第七天|力扣334.反转字符串、力扣541.反转字符串II、剑指offer05
    字符串反转字符串(力扣344.)如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。毕竟面试官一定不是考察你对库函数的熟悉程度,如果使用python和java的同学更需要注意这一点,因为python、java提供的库函数十分丰富。如果库函数仅仅是解题过程中的一小部分,并且......
  • AP2400 LED照明电源驱动 DC-DC降压恒流IC 过EMC线路图 PCB线路图 车灯摩灯
    产品特点宽输入电压范围:5V~100V可设定电流范围:10mA~6000mA固定工作频率:150KHZ内置抖频电路,降低对其他设备的EMI干扰平均电流模式采样,恒流精度更高0-100%占空比控制,无电流节点跳变输出短路保护过温保护三功能模式:全亮/半亮/爆闪/三功能循环SOP8封装产品描述AP2400是一款PWM工作模......
  • .NetCore + Selenium IIS 部署踩坑记
    一、问题   使用Selenium+chromedriver开发自动操作页面demo,本地调试使用IISExpress正常,部署到IIS访问接口代码正常执行,但是,但是页面并没有启动二、排查  网上找相似情况大概以下几种 1,chromedriver和chrome的版本不一致 2,IIS用户权限 3,代码写法问题 本......
  • 代码随想录算法训练营第六天|力扣454.四数相加II、力扣383.赎金信、力扣15.三数之和、
    四数相加II(力扣454.)前两个数组的值直接遍历,并将和存入map中,key为和,value为出现次数后两个数组再次遍历,在map中寻找是否存在0-(c+d),若存在,count+=valuefor(a:A){//遍历ABfor(b:B){map[a+b]++;}}//insert操作for(c:C){for(d:D){target=0-(c+d);if(map.containsKey(t......