首页 > 其他分享 >[LeetCode Hot 100] LeetCode74. 搜索二维矩阵

[LeetCode Hot 100] LeetCode74. 搜索二维矩阵

时间:2023-12-21 12:15:12浏览次数:40  
标签:index matrix LeetCode74 int 二维 Hot 坐标 length 100

题目描述

思路:二维矩阵坐标变换 + 二分查找

二维矩阵坐标变换
只要知道二维数组的的行数m和列数n,二维数组的坐标 (i, j) 可以映射成一维的index = i * n + j;反过来也可以通过一维index反解出二维坐标 i = index / n,j = index % n(n是列数)

把二维数组matrix的元素访问抽象成在一维数组中访问元素,然后直接施展最基本的二分搜索即可。

方法一:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == get(matrix, mid)) {
                return true;
            } else if (target < get(matrix, mid)) {
                right = mid - 1;
            } else if (target > get(matrix, mid)) {
                left = mid + 1;
            }
        }
        return false;
    }

    // 通过一维坐标访问二维数组中的元素
    private int get(int[][] matrix, int index) {
        int n = matrix[0].length;
        // 计算坐标
        int i = index / n, j = index % n;
        return matrix[i][j];
    }
}

标签:index,matrix,LeetCode74,int,二维,Hot,坐标,length,100
From: https://www.cnblogs.com/keyongkang/p/17918676.html

相关文章

  • 初中英语优秀范文100篇-033My Free Time-我的业余时间
    PDF格式公众号回复关键字:SHCZFW033记忆树1Ihavealotofthingstodoinmyfreetime.翻译我有很多空闲时间要做的事情。简化记忆事情句子结构主语(I):表示句子中的主体,即说话者本人。谓语(have):表示主体所进行的动作或状态,这里是“有”的意思。宾语(alotofthing......
  • Java中“100==100”为true,而"1000==1000"为false?
    前言今天跟大家聊一个有趣的话题,在Java中两个Integer对象做比较时,会产生意想不到的结果。例如:Integera=100;Integerb=100;System.out.println(a==b);其运行结果是:true。而如果改成下面这样:Integera=1000;Integerb=1000;System.out.println(a==b);其运行......
  • [LeetCode Hot 100] LeetCode153. 寻找旋转排序数组中的最小值
    题目描述思路如果数组翻转后又回到升序的情况,即nums[left]<=nums[right],则nums[left]就是最小值,直接返回。如果数组翻转,需要找到数组中第二部分的第一个元素:若nums[left]<=nums[mid],说明区间[left,mid]连续递增,则最小元素一定不在这个区间里,可以直接排除,最小值在[......
  • 初中英语优秀范文100篇-032My Favourite Season-我最喜欢的季节
    PDF格式公众号回复关键字:SHCZFW032记忆树1Autumnismyfavouriteseason.翻译秋天是我最喜欢的季节。简化记忆秋天句子结构"Autumn"是主语,表示秋天这个季节。"is"是系动词,连接主语和表语。"myfavouriteseason"是表语,表示秋天使我最喜欢的季节。其中,"my"是形容......
  • 100道React高频题整理(附答案背诵版)
    1、简述React有什么特点?React是一个用于构建用户界面的JavaScript库,由Facebook开发并维护。React有以下几个主要特点:声明式设计:React采用声明式设计,让代码更易于理解,且方便调试。你只需描述出你希望程序的最终状态,React会自动确保用户界面与你描述的状态保持一致。组件化:......
  • [LeetCode Hot 100] LeetCode33. 搜索旋转排序数组
    题目描述思路如果nums[left]<=nums[mid],则[left,mid]有序如果nums[left]>nums[mid],则[mid,right]有序方法一:classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0)return-1;intleft=0,ri......
  • [LeetCode Hot 100] LeetCode35. 搜索插入位置
    题目描述思路基础二分搜索模板本质:找到第一个大于等于target的元素的下标注意:该题目不存在重复元素存在一种特殊情况:target>nums的最大值,此时插入的位置正好是left的位置方法一:classSolution{publicintsearchInsert(int[]nums,inttarget){if......
  • [LeetCode Hot 100] LeetCode34.在排序数组中查找元素的第一个和最后一个位置
    题目描述思路:二分查找之寻找左右侧边界两个关键点:1.数组有序;2.时间复杂度O(logn)方法一:classSolution{publicint[]searchRange(int[]nums,inttarget){if(nums.length==0||nums==null){returnnewint[]{-1,-1};}......
  • 记录--一行代码修复100vh bug
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助你知道奇怪的移动视口错误(也称为100vhbug)吗?或者如何以正确的方式创建全屏块?一、100vhbug什么是移动视口错误?你是否曾经在网页上创建过全屏元素?只需添加一行CSS并不难:.my-page{height:100vh}1v......
  • 【2023潇湘夜雨】WIN11_Pro_Canary_26016.1000软件选装纯净版12.19
    【系统简介】=============================================================1.本次更新母盘来自WIN11_Pro_Canary_26016.1000。2.增加部分优化方案,手工精简部分较多,干掉右下角水印。3.OS版本号为26016.1000。精简系统只是为部分用户安装,个别要求高的去MSDN下。4.集成《DrvCeo-2.1......