剑指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.…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

Qt的学习(二)
1. 创建Hello Word 两种方式,实现helloworld: 1.通过图形化的方式,在界面上创建出一个控件,显示helloworld 2.通过纯代码的方式,通过编写代码,在界面上创建控件, 显示hello world; …...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...

Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...
npm install 相关命令
npm install 相关命令 基本安装命令 # 安装 package.json 中列出的所有依赖 npm install npm i # 简写形式# 安装特定包 npm install <package-name># 安装特定版本 npm install <package-name><version>依赖类型选项 # 安装为生产依赖(默认&…...