剑指offer面试题3 二维数组中的查找
考察点:
考察数据结构二维数组
知识点:
1.java中的数据类型分为基本类型和引用类型,数组属于引用类型,引用类型的变量中存储的是地址,该地址指向内存中的某个对象,参考c中的指针。2.一维数组定义,初始化,遍历2.1.先定义后初始化:尤其注意如果只定义没有初始化那么元素会被初始化为数据类型的默认值,int会被初始化为0,float会被初始化为0.0,boolean会被初始化为falseint arr[] = new int[2];arr[0] = 10;2.2.定义的时候同时初始化:int arr[] = {1,2};int arr[] = new int[] {1,2};2.3.数组遍历2.3.1.for (int i = 0;i < arr.length;i++) {System.out.println(arr[i]);}2.3.2.for (int a : arr) {System.out.println(a);}2.3.3.java标准库System.out.println(Arrays.toString(arr));3.二维数组定义,初始化,遍历3.1.先定义后初始化int arr[][] = new int[2][3];int brr[] = new int[3];int crr[] = new int[3];arr[0] = brr;arr[1] = crr;注意此时arr.length = 2,而arr[0].length = 0,arr[1].length = 0;3.2.定义的时候同时初始化int arr[][] = {{1,2,3},{4,5,6},{7,8,9}}3.3.数组的遍历3.3.1 for (int i = 0;i < arr.length; i++) {for (int j = 0;j<arr[0].length;j++) {System.out.println(arr[i][j]);}}3.3.2.for (int brr[] : arr) {for (int n : brr) {System.out,println(n);}}
题目:
分析:
关于数组这个数据结构的考点无非就是数组遍历。本题目要求判断一个二维数组中是否含有某一个数字,直接遍历二维数组也可以满足需求,但此种解法复杂度为O(n^2),题目不会这么简单,那延伸一下考察的点无非就是如何提升遍历的效率,试想一下每次二维数组一个循环只能遍历掉一个元素,如果一个循环遍历掉一块元素的话,那效率就会极大的提升。仔细观察题目,其中设定了数组的一些属性,那么这些属性的目的大概率就是冲着减少遍历元素的目的去的。每行每列都是递增排序,试想如果一行(或者一列)中最大的那个元素比待查找的元素小,那这个待查找的值肯定不会出现在这个最大元素所在的行(或者列);如果一行(或者一列)中最小的那个元素比待查找的元素大,那么这个待查找的值也肯定不会出现在这个最小元素所在的行(或者列)。而题目中的这个二维数组中左上角和右下角的元素就满足这样的特性,因为左上角元素是行的最大值列的最小值,右下角是行的最小值列的最大值,拿左上角举例,如果该元素比待查找的元素小,那么这个元素所在的行就可以不用遍历了,如果该元素比待查找的元素大,那么这个元素所在的列就可以不用遍历了。
代码:
public class Three {public static void main(String [] args) {int arr[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};System.out.println(find(arr,arr.length,arr[0].length,7));System.out.println(find(arr,arr.length,arr[0].length,71));int brr[][] = new int[0][0];System.out.println(find(brr,brr.length,0,71));int crr[][] = new int[1][0];crr[0] = new int[0];System.out.println(find(crr,crr.length,crr[0].length,71));}public static boolean find(int [][] arr,int rows,int cols,int val) {if (null == arr || arr.length == 0|| (arr.length == 1 && arr[0].length == 0)|| rows <=0 || cols <= 0) {return false;}int row = 0;int col = cols - 1;while (row < rows && col >=0) {if (arr[row][col] == val) {return true;}if (arr[row][col] < val) {row ++;} else {col --;}}return false;}
}
相关文章:
剑指offer面试题3 二维数组中的查找
考察点: 考察数据结构二维数组知识点: 1.java中的数据类型分为基本类型和引用类型,数组属于引用类型,引用类型的变量中存储的是地址,该地址指向内存中的某个对象,参考c中的指针。2.一维数组定义,…...

【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现
【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现 更新时间:2023-12-29 1 题目 赛题 B DNA 存储中的序列聚类与比对 近年来,随着新互联网设备的大量涌入和对其服务需求的指数级增长,越来越多的数据信息被产…...

力扣383.赎金信 -- 哈希表
思路:记录magazine每个字符个数,然后记录ransomNote每个字符(每有一个减1),假如出现<0的情况说明ransomnode有字符的个数超过了magazine则无法构成,否则可以构成 代码: class Solution { pu…...

GeoServer发布地图服务(WMS、WFS)
文章目录 1. 概述2. 矢量数据源3. 栅格数据源 1. 概述 我们知道将GIS数据大致分成矢量数据和栅格数据(地形和三维模型都是兼具矢量和栅格数据的特性)。但是如果用来Web环境中,那么使用图片这个栅格形式的数据载体无疑是最为方便的࿰…...

C语言——结构体
一、结构体的创建 1、定义 在 C 语言中,结构体是一种自定义的数据类型,它允许将不同类型的数据项组合成一个单一实体。这在组织复杂数据时非常有用,因为它可以将有逻辑关系的数据组合在一起。结构体是一些值的集合,这些值是结构…...

基于多反应堆的高并发服务器【C/C++/Reactor】(中)Buffer的创建和销毁、扩容、写入数据
TcpConnection:封装的就是建立连接之后得到的用于通信的文件描述符,然后基于这个文件描述符,在发送数据的时候,需要把数据先写入到一块内存里边,然后再把这块内存里边的数据发送给客户端,除了发送数据,剩下…...

【Linux】常用的基本命令指令①
前言:从今天开始,我们逐步的学习Linux中的内容,和一些网络的基本概念,各位一起努力呐! 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码…...
活动运营常用的ChatGPT通用提示词模板
活动目标确定:如何明确活动的目标,确保活动策划与执行的方向性? 活动主题选择:如何选择吸引人的活动主题,提高用户的参与度和兴趣? 活动形式策划:如何根据活动目标和主题,选择适合…...
SpringBoot 中实现订单30分钟自动取消的策略
简介 在电商和其他涉及到在线支付的应用中,通常需要实现一个功能:如果用户在生成订单后的一定时间内未完成支付,系统将自动取消该订单。 本文将详细介绍基于Spring Boot框架实现订单30分钟内未支付自动取消的几种方案,并提供实例…...

像专家一样使用TypeScript映射类型
掌握TypeScript的映射类型,了解TypeScript内置的实用类型是如何工作的。 您是否使用过Partial、Required、Readonly和Pick实用程序类型? 你知道他们内部是怎么运作的吗? 如果您想彻底掌握它们并创建自己的实用程序类型,那么不要错过本文所涵盖的内容。…...
Golang 结构体
前言 在 Go 语言中,结构体(struct)是一种自定义的数据类型,将多个不同类型的字段(fields)组合在一起 结构体通常用于模拟真实世界对象的属性和行为 定义结构体 可以使用 type 关键字和 struct 关键字来定…...

服务器运行状况监控工具
服务器运行状况监视提供了每个服务器状态和性能的广泛概述,通过监控服务器指标,如 CPU 使用率、内存消耗、I/O、磁盘使用率、进程等,服务器运行状况监控可以避免服务器停机。 服务器性能监控指标 服务器是网络中最重要的组件之一࿰…...
2022年全国职业院校技能大赛软件测试赛题卷②—自动化测试解析报告(含术语)
2022年全国职业院校技能大赛软件测试任务四 自动化测试 目录 第一题:按照以下步骤在PyCharm中进行自动化测试脚本编写,并执行脚本。...

497 蓝桥杯 成绩分析 简单
497 蓝桥杯 成绩分析 简单 //C风格解法1,*max_element()与*min_element()求最值 //时间复杂度O(n),通过率100% #include <bits/stdc.h> using namespace std;using ll long long; const int N 1e4 …...

一、HTML5简介
一、简介 超文本标记语言(英语:HyperText Markup Language,简称:HTML)是一种用于创建网页的标准标记语言。可以使用 HTML 来建立自己的 WEB 站点,HTML 运行在浏览器上,由浏览器来解析。 <!…...

视频云存储/视频智能分析平台EasyCVR在麒麟系统中无法启动该如何解决?
安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等,以及支持厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…...

前端性能优化之图像优化
图像优化问题主要可以分为两方面:图像的选取和使用,图像的加载和显示。 图像基础 HTTP Archive上的数据显示,网站传输的数据中,60%的资源都是由各种图像文件组成的,当然这些是将各类型网站平均的结果,单独…...

微信小程序封装vant 下拉框select 单选组件
先上效果图: 主要是用vant 小程序组件封装的:vant 小程序ui网址:vant-weapp 主要代码如下: 先封装子组件: select-popup 放在 components 文件夹里面 select-popup.wxml: <!--pages/select-popup/select-popup.wxml--> &…...
c语言试卷
江西财经大学IT帮 2020-2021第一学期期末C语言模拟考试试卷 课程名称:C语言程序设计(软件)(主干课程) 适用对象:21级本科 试卷命题人 钟芳盛 游天悦 李俊贤 万军豪 张位 试卷审核人 钟芳盛 一、单项…...

文献阅读:Sparse Low-rank Adaptation of Pre-trained Language Models
文献阅读:Sparse Low-rank Adaptation of Pre-trained Language Models 1. 文章简介2. 具体方法介绍 1. SoRA具体结构2. 阈值选取考察 3. 实验 & 结论 1. 基础实验 1. 实验设置2. 结果分析 2. 细节讨论 1. 稀疏度分析2. rank分析3. 参数位置分析4. 效率考察 4.…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...