Java查找算法知识点(含面试大厂题和源码)
查找算法是计算机科学中的基础概念,它们在解决实际问题时扮演着关键角色。了解和掌握不同的查找算法,能够帮助我们更高效地处理数据检索任务。以下是一些关于查找算法的关键知识点:
-
算法分类:
- 线性查找算法:按照顺序逐个检查元素,直到找到目标或遍历完毕。
- 二分查找算法:在有序集合中使用,通过不断缩小搜索范围来查找目标元素。
- 插值查找算法:适用于均匀分布的有序集合,通过预测目标元素的位置来加快查找速度。
- 哈希查找算法:使用哈希表进行查找,通过哈希函数将关键字映射到表中一个位置。
- 树形查找算法:如二叉搜索树、B树、B+树等,通过树形结构来组织数据,加快查找速度。
-
时间复杂度:
- 线性查找的时间复杂度为 O(n)。
- 二分查找的时间复杂度为 O(log n)。
- 插值查找在最理想情况下可以达到 O(log log n),但在最坏情况下会退化为 O(n)。
- 哈希查找的理想时间复杂度为 O(1),但在处理哈希冲突时可能退化为 O(n)。
- 树形查找算法的时间复杂度依赖于树的高度,平衡树形结构的平均时间复杂度为 O(log n)。
-
空间复杂度:
- 线性查找不需要额外空间或只需要常数级别的额外空间。
- 二分查找和插值查找的空间复杂度为 O(1)。
- 哈希查找的空间复杂度取决于哈希表的大小和装填因子。
- 树形查找算法的空间复杂度取决于树的高度和节点的分支数。
-
适用场景:
- 线性查找适用于小型数据集或无序数据集。
- 二分查找和插值查找适用于大型的有序数据集。
- 哈希查找适用于无序数据集,且查询操作非常频繁的场景。
- 树形查找算法适用于处理大量数据,并且需要频繁插入、删除和查找操作的场景。
-
优化策略:
- 对于线性查找,可以通过减少数据集的大小或改进数据存储结构来优化。
- 二分查找和插值查找的优化通常涉及到如何选择一个好的有序数组或如何设计一个高效的哈希函数。
- 哈希查找的优化通常涉及到如何处理哈希冲突,例如开放寻址法、链地址法等。
- 树形查找算法的优化通常涉及到如何保持树的平衡,例如 AVL 树、红黑树等。
-
哈希冲突:
- 哈希冲突是指两个或多个不同的关键字产生相同的哈希值。
- 解决哈希冲突的方法包括开放寻址法、链地址法、再散列法等。
-
动态查找:
- 动态查找是指在查找过程中动态地更新查找表,包括插入、删除和修改操作。
掌握这些查找算法的知识点,可以帮助我们在面对不同的数据检索问题时,选择最合适的算法来解决问题。在实际应用中,算法的选择往往需要综合考虑时间复杂度、空间复杂度、数据的特点和操作的频率等因素。查找算法是计算机科学中的一类算法,用于在数据结构中查找特定的元素或者满足特定条件的元素。查找算法的效率对于程序的整体性能有着重要的影响。以下是几种常见的查找算法,以及它们的基本原理和适用场景。
1. 线性查找(Linear Search)
基本原理:线性查找是最简单的查找算法。它从数据结构的一端开始,逐个检查每个元素,直到找到目标元素或者遍历完整个数据结构。
时间复杂度:O(n),其中 n 是数据结构中元素的数量。
适用场景:适用于无序数据集的查找,或者数据量较小的情况下。
Java 示例:
public static int linearSearch(int[] array, int target) {for (int i = 0; i < array.length; i++) {if (array[i] == target) {return i;}}return -1; // 表示未找到目标元素
}
2. 二分查找(Binary Search)
基本原理:二分查找是一种在有序数据集上进行的查找算法。它每次将数据集分为两部分,并比较中间元素与目标值,根据比较结果决定是继续在左侧子集查找还是右侧子集查找。
时间复杂度:O(log n)。
适用场景:适用于有序数据集的查找,效率较高。
Java 示例:
public static int binarySearch(int[] array, int target) {int left = 0;int right = array.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == target) {return mid;} else if (array[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 表示未找到目标元素
}
3. 插值查找(Interpolation Search)
基本原理:插值查找是二分查找的一种改进,适用于数据分布均匀的有序数据集。它根据目标值在数据集中的估计位置来查找,而不是简单地每次都将数据集分为两部分。
时间复杂度:在数据分布均匀的情况下,平均时间复杂度为 O(log log n)。
适用场景:适用于数据量大且分布均匀的有序数据集。
Java 示例:
public static int interpolationSearch(int[] array, int target) {int left = 0;int right = array.length - 1;while (left <= right && target >= array[left] && target <= array[right]) {int pos = left + ((target - array[left]) * (right - left)) / (array[right] - array[left]);if (array[pos] == target) {return pos;}if (array[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1; // 表示未找到目标元素
}
4. 哈希查找(Hash Search)
基本原理:哈希查找是通过哈希表进行的查找算法。它通过哈希函数将关键字映射到哈希表的一个位置,从而实现快速查找。
时间复杂度:理想情况下为 O(1),但在哈希冲突的情况下可能退化为 O(n)。
适用场景:适用于无序数据集的快速查找,特别是当数据量很大时。
Java 示例:
import java.util.HashMap;
import java.util.Map;public static int hashSearch(Map<Integer, Integer> map, int target) {return map.containsKey(target) ? map.get(target) : -1; // 表示未找到目标元素
}// 示例用法
Map<Integer, Integer> map = new HashMap<>();
// 假设 map 已经被填充了数据
int result = hashSearch(map, targetValue);
以上是几种常见的查找算法,它们各有优势和适用场景。在实际应用中,选择合适的查找算法可以显著提高程序的查找效率。
相关文章:
Java查找算法知识点(含面试大厂题和源码)
查找算法是计算机科学中的基础概念,它们在解决实际问题时扮演着关键角色。了解和掌握不同的查找算法,能够帮助我们更高效地处理数据检索任务。以下是一些关于查找算法的关键知识点: 算法分类: 线性查找算法:按照顺序逐…...

67、yolov8目标检测和旋转目标检测算法部署Atlas 200I DK A2开发板上
基本思想:需求部署yolov8目标检测和旋转目标检测算法部署atlas 200dk 开发板上 一、转换模型 链接: https://pan.baidu.com/s/1hJPX2QvybI4AGgeJKO6QgQ?pwdq2s5 提取码: q2s5 from ultralytics import YOLO# Load a model model YOLO("yolov8s.yaml")…...

A Little Is Enough: Circumventing Defenses For Distributed Learning
联邦学习的攻击方法:LIE 简单的总结,只是为了能快速想起来这个方法。 无目标攻击 例如总共50个客户端,有24个恶意客户端,那么这个时候,他需要拉拢2个良性客户端 计算 50 − 24 − 2 50 − 24 0.923 \frac{50-24-2}{…...

文心一言 VS 讯飞星火 VS chatgpt (225)-- 算法导论16.3 7题
七、推广赫夫曼算法,使之能生成三进制的码字(即码字由符号0、1、2组成),并证明你的算法能生成最优三进制码。如果要写代码,请用go语言。 文心一言: 推广赫夫曼算法以生成三进制码字需要对算法进行一定的修改,确保在每…...

【计算机】——51单片机——持续更新
单片机是一种内部包含CPU、存储器和输入/输出接口等电路的集成电路(IC芯片) 单片机是单片微型计算机(Single Chip Microcomputer)的简称,用于控制领域,所以又称为微型控制器(Microcontroller U…...

QT资源添加调用
添加资源文件,新建资源文件夹,命名resource,然后点下一步,点完成 资源,右键add Prefix 添加现有文件 展示的label图片切换 QLabel *led_show; #include "mainwindow.h" #include<QLabel> #include&l…...
LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】
LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】 题目描述:解题思路一:哈希表和排序,这里最关键的点是,乱序单词的排序结果必然是一样的(从而构成哈希表的key)。解题思路二:解题思路三…...

绘制特征曲线-ROC(Machine Learning 研习十七)
接收者操作特征曲线(ROC)是二元分类器的另一个常用工具。它与精确度/召回率曲线非常相似,但 ROC 曲线不是绘制精确度与召回率的关系曲线,而是绘制真阳性率(召回率的另一个名称)与假阳性率(FPR&a…...

.Net 知识杂记
记录平日中琐碎的.net 知识点。不定期更新 目标框架名称(TFM) 我们创建C#应用程序时,在项目的工程文件(*.csproj)中都有targetFramework标签,以表示项目使用的目标框架 各种版本的TFM .NET Framework .NET Standard .NET5 及更高版本 UMP等 参考文档&a…...

海豚【货运系统源码】货运小程序【用户端+司机端app】源码物流系统搬家系统源码师傅接单
技术栈:前端uniapp后端vuethinkphp 主要功能: 不通车型配置不通价格参数 多城市定位服务 支持发货地 途径地 目的地智能费用计算 支持日期时间 预约下单 支持添加跟单人数选择 支持下单优惠券抵扣 支持司机收藏订单评价 支持订单状态消息通知 支…...

01---java面试八股文——mybatis-------10题
1、什么是MyBatis Mybatis是一个半ORM(对象关系映射)框架,它内部封装了JDBC,开发时只需要关注SQL语句本身,不需要花费精力去处理加载驱动、创建连接、创建statement等繁杂的过程。程序员直接编写原生态sql,…...

增强现实(AR)的开发工具
增强现实(AR)的开发工具涵盖了一系列的软件和平台,它们可以帮助开发者创造出能够将虚拟内容融入现实世界的应用程序。以下是一些在AR领域内广泛使用的开发工具。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎…...

用Unity制作正六边形拼成的地面
目录 效果演示 1.在Unity中创建正六边形 2.创建一个用于管理正六边形的类 3.创建一个用于管理正六边形地面的类 4.创建一个空对象并将游戏控制脚本挂上 5.设置正六边形碰撞所需组件 6.创建正六边形行为触发脚本并挂上 7.创建圆柱体——田伯光 8.创建圆柱体移动脚本 运…...
Spark部署详细教程
Spark Local环境部署 下载地址 https://dlcdn.apache.org/spark/spark-3.4.2/spark-3.4.2-bin-hadoop3.tgz 条件 PYTHON 推荐3.8JDK 1.8 Anaconda On Linux 安装 本次课程的Python环境需要安装到Linux(虚拟机)和Windows(本机)上 参见最下方, 附: Anaconda On Linux 安装…...

慧天[HTWATER]:创新城市水务科技,引领行业变革
【城市内涝水文水动力模型介绍】 慧天[HTWATER]软件:慧天排水数字化分析平台针对城市排水系统基础设施数据管理的需求,以及水文、水力及水质模拟对数据的需求,实现了以数据库方式对相应数据的存储。可以对分流制排水系统及合流制排水系统进行…...

vscode调试Unity
文章目录 vscode调试UnityC#环境需求开始调试 Lua添加Debugger环境配置联系.txt文件配置Java环境 添加调试代码断点不生效的问题 vscode调试Unity C# 现在使用vscode调试Unity的C#代码很简单,直接在vscode的EXTENSIONS里面搜索“Unity”,第一个就是&am…...
JavaScript是如何实现页面渲染的
JavaScript实现页面渲染主要涉及到对DOM的操作、样式的修改以及与后端数据的交互。以下是JavaScript实现页面渲染的主要步骤和方式: 一、DOM操作 创建和修改元素:JavaScript可以使用document.createElement()来创建新的DOM元素,使用appendC…...

【YOLOv8 代码解读】数据增强代码梳理
1. LetterBox增强 当输入图片的尺寸和模型实际接收的尺寸可能不一致时,通常需要使用LetterBox增强技术。具体步骤是先将图片按比例缩放,将较长的边缩放到设定的尺寸以后,再将较短的边进行填充,最终短边的长度为stride的倍数即可。…...

安卓调试桥ADB
Logcat 命令行工具 | Android Studio | Android Developers 什么是ADB ADB 全称为 Android Debug Bridge ,是 Android SDK (安卓的开发工具)中的一个工具,起到调试桥的作用,是一个 客户端 - 服务器端程序 。其中 …...

深入理解数据结构第一弹——二叉树(1)——堆
前言: 在前面我们已经学习了数据结构的基础操作:顺序表和链表及其相关内容,今天我们来学一点有些难度的知识——数据结构中的二叉树,今天我们先来学习二叉树中堆的知识,这部分内容还是非常有意思的,下面我们…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...