首页 > 其他分享 >240. 搜索二维矩阵 II(中)

240. 搜索二维矩阵 II(中)

时间:2024-11-08 20:19:37浏览次数:4  
标签:二分 return target 矩阵 II length 查找 240 matrix

目录

题目

  • 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。

法一、暴力

var searchMatrix = function(matrix, target) {
    let m=matrix.length,n=matrix[0].length
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if (target==matrix[i][j]){
                return true
            }
        }
    }
    return false
};
  • 超出时间限制,时间复杂度:O(mn)。

法二、二分查找

  • 每一行都是升序,对每一行进行二分查找
var searchMatrix = function(matrix, target) {
    for(const row of matrix){
        const index = search(row,target)
        if (index >= 0){
            return true
        }
    }
    return false
};

const search = (nums,target)=>{
    let low=0,high = nums.length -1
    while(low<=high){
        const mid = Math.floor((high-low)/2)+low
        const num = nums[mid]
        if(num === target){
            return mid
        }else if(num>target){
            high=mid-1
        }else{
            low=mid+1
        }
    }
    return -1
}
  • 超出时间限制,时间复杂度:O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn),最多需要进行 m 次二分查找。

法三、Z 字形查找

  • 每一行都是升序,对每一行进行二分查找
var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let x = 0, y = n - 1;//右上角开始
    while (x < m && y >= 0) {
        if (matrix[x][y] === target) {
            return true;
        }
        if (matrix[x][y] > target) {//当前元素大于目标值,其这一列的下面元素都大于,不考虑
            --y;
        } else {//当前元素小于目标值,其这一行的左边元素都小于,不考虑
            ++x;
        }
    }
    return false;
};

标签:二分,return,target,矩阵,II,length,查找,240,matrix
From: https://www.cnblogs.com/lushuang55/p/18535809

相关文章

  • 代码随想录算法训练营day39 day40| 198.打家劫舍 213.打家劫舍II 337.打家劫舍III
    学习资料:https://programmercarl.com/0198.打家劫舍.html#算法公开课动态规划的打家劫舍系列和股票买卖系列(股票还有贪心算法可解)学习记录:198.打家劫舍(一维dp数组,前n间房子都可偷的情况下的最高金额,每间房子偷数都是由前一间和前两间决定)点击查看代码classSolution(object)......
  • C++——求一个3*3矩阵主对角线元素之和。
    没注释的源代码#include<iostream>usingnamespacestd;intmain(){   inta[3][3],sum=0;   cout<<"pleaseinputmartix:"<<endl;   for(inti=0;i<3;i++)   {       for(intj=0;j<3;j++)       {           cin......
  • 第八章: 8.10将一个5*5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(四个角的元
    第八章:8.10将一个5*5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(四个角的元素的顺序是从左到右,从上到下,依次从小到大存放)思考:1.输入矩阵的值inta[5][5]={0};   inti=0,j=0;   printf("请输入一个5*5的数组:\n");   for(i=0;i<5;......
  • 第二届生成式人工智能与信息安全国际学术会议(GAIIS 2025)
    第二届生成式人工智能与信息安全国际学术会议(GAIIS2025) 会议时间与地点:2025年2月21日至23日,中国杭州。会议主题:围绕“生成式人工智能与信息安全”的最新研究,聚焦AI热点和难点问题,深入剖析信息安全核心技术。大会主席:DongXu,UniversityofMissouri-Columbia,USA姚信......
  • 20240928 模拟赛
    20240928模拟赛Agenius将模运算转化,\(\sum_{i=1}^{n}a_i\bmodk=\sum_{i=1}^{n}(a_i-\lfloor\frac{a_i}{k}\rfloor\timesk)=sum-k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor=s\)。移项得到\(sum-s=k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor\)。于是\(sum-s\)是......
  • 20240925 模拟赛
    20240925模拟赛Apow显然如果出现了\(1\),那么\(1\)和后面的数都没用了。于是剩下的数不小于\(2\)。考虑\(3\)个数的情况,只有\(a^{(b^c)}\)和\((a^b)^c\)两种情况。第二中等价于\(a^{bc}\),注意到当\(b,c\geq2\)时\(b^c\geqbc\),于是第一种情况一定不优,所以直接......
  • 20240923 分块莫队专题
    20240923分块莫队专题回滚莫队回滚莫队适用于添加与删除中有一种较为困难的情况。大致思想如下:对原序列分块,将询问按左端点所在块编号排序,同一块内按右端点排序。对每个块,视情况初始化左右指针,扫一遍询问。先移动右指针到询问右端点,记录当前状态的答案,再将左指针移到询问左端......
  • 20240919 短时赛
    20240919短时训练赛AShuffle赛时一直不知道怎么不重,唐了两个小时。注意到\(n\leq5000\),那么先\(O(n^2)\)枚举发生变化的第一个数和最后一个数,这两个位置不同时方案显然不同,于是不会算重。发生变化的这两个数强制改,剩下的乱放,组合数算一下就好。BRainCXORTree注......
  • 20240918 模拟赛
    20240918模拟赛AStringBPack看这个数据范围很容易想到dp,设\(f_{i,,j,k}\)(pair<int,int>)表示前\(i\)个物品,拿走\(j\)个\(1\),\(k\)个\(2\)所用的最少车数,以及最后一辆车所用的最少空间。转移分当前这个拿不拿掉讨论,非常显然。最后枚举总共拿了几个\(1\)和几个......
  • 20240914 模拟赛
    20240914模拟赛A开挂(openhook)可以发现结果序列是能确定的,而且我们并不关心具体对哪个数进行操作,有用的信息只有操作次数,从而可以得到一个数组\(c\)表示对某个数操作了某个次数。设对\(tot\)个数进行了操作,将\(c\)从小到大排序,将\(b\)中的前\(tot\)小从大到小排序,于......