Java查找算法练习(2024.7.23)
顺序查找
package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入想要查找的元素");int key = sc.nextInt();int result = searchElement(array, key);if (result != -1) {System.out.println("成功找到");System.out.printf("该元素的下标是%d", result);} else {System.out.println("数组中没有该元素");}}public static int searchElement(int[] array, int key) {for (int i = 0; i < array.length; i++) {if (array[i] == key) {return i;}}return -1;}// 这是最简单的查找,效率为O(n)
}
二分查找
package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int flag = searchImprove(array, key);if (flag == -1) {System.out.println("数组中没有该元素");} else {System.out.println("查找成功,下标是" + flag);}}// 二分查找,使用十分的广泛,时间复杂度是O(log2n),但是二分查找需要元素有序才可以使用public static int searchImprove(int[] array, int key) {int low = 0;int high = array.length - 1;while (low <= high) {int mid = (low + high) / 2;if (array[mid] > key) {high = mid - 1;} else if(array[mid] < key) {low = mid + 1;} else {return mid;}}return -1;}
}
插值查找(二分查找的改进)
package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise3 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int flag = searchImprove(array, key);if (flag == -1) {System.out.println("数组中没有该元素");} else {System.out.println("查找成功,下标是" + flag);}}// 插值查找,通过将每次查找的点进行改进(mid),让mid值的变化更靠近关键字key,可以间接的减少比较的次数// 细节:和二分查找几乎一样,除了对于mid的计算不同,所以说插值查找也需要查找表有序// 并且对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多,// 但是对于分布不均匀的查找表,插值查找不建议选择public static int searchImprove(int[] array, int key) {int low = 0;int high = array.length - 1;while (low <= high) {int mid = low+((key-array[low])*(high-low))/(array[high]-array[low]);// 改变了mid的计算,使得让mid的变化更加接近查找关键字if (array[mid] > key) {high = mid - 1;} else if (array[mid] < key) {low = mid + 1;} else {return mid;}}return -1;}
}
斐波那契查找
package SearchExercise20240723;
import java.util.Arrays;
import java.util.Scanner;
public class SearchExercise4 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int result = fibSearch(key, array);if (result == -1) {System.out.println("数组中没有这个元素");} else {System.out.println("成功找到,下标是" + result);}}public static int[] creatFib() {int[] arr = new int[20];arr[0] = 1;arr[1] = 1;for (int i = 2; i < 20; i++) {arr[i] = arr[i - 1] + arr[i - 2];}return arr;}public static int fibSearch(int key, int[] arr) {int low = 0;int high = arr.length - 1;//表示斐波那契数分割数的下标值int index = 0;int mid = 0;//调用斐波那契数列int[] f = creatFib();//获取斐波那契分割数值的下标while (high > (f[index] - 1)) {index++;}//因为f[k]值可能大于a的长度,因此需要使用Arrays工具类,构造一个新法数组,并指向temp[],不足的部分会使用0补齐int[] temp = Arrays.copyOf(arr, f[index]);//实际需要使用arr数组的最后一个数来填充不足的部分for (int i = high + 1; i < temp.length; i++) {temp[i] = arr[high];}//使用while循环处理,找到key值while (low <= high) {mid = low + f[index - 1] - 1;if (key < temp[mid]) {//向数组的前面部分进行查找high = mid - 1;/*对k--进行理解1.全部元素=前面的元素+后面的元素2.f[k]=k[k-1]+f[k-2]因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]即在f[k-1]的前面继续查找k--即下次循环,mid=f[k-1-1]-1*/index--;} else if (key > temp[mid]) {//向数组的后面的部分进行查找low = mid + 1;index -= 2;} else {//找到了//需要确定返回的是哪个下标if (mid <= high) {return mid;} else {return high;}}}return -1;}
}
分块查找
package SearchExercise20240723;
import java.util.Arrays;
import java.util.Scanner;
public class SearchExercise5 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}// 创建索引表int blockSize = (int)Math.sqrt(array.length);Block[] blocksArray = creatBlocksArray(array, blockSize);// 分块查找System.out.println("请输入要查找的元素");int key = sc.nextInt();int result = blockSearch(array, blocksArray, key);if (result == -1) {System.out.println("数组中无法找到该元素");} else {System.out.printf("成功找到,下标是%d", result);}}public static Block[] creatBlocksArray(int[] array, int blockSize) {int blockNumbers = (int)Math.ceil(array.length * 1.0 / blockSize);Block[] blockArray = new Block[blockNumbers];for (int i = 0; i < blockArray.length; i++) {int start = i * blockSize;int end = Math.min(start + blockSize, array.length);int maxKey = Arrays.stream(array, start, end).max().orElse(Integer.MIN_VALUE);blockArray[i] = new Block(start, end, maxKey);}return blockArray;}public static int blockSearch(int[] array, Block[] blocksArray, int key) {int blockIndex = -1;for (int i = 0; i < blocksArray.length; i++) {if (key <= blocksArray[i].getMaxKey()) {blockIndex = i;break;}}if (blockIndex == -1) {return -1;}int start = blocksArray[blockIndex].getStart();int end = blocksArray[blockIndex].getEnd();for (int i = start; i < end; i++) {if(array[i] == key){return i;}}return -1;}
}class Block{private int start;private int end;private int maxKey;public Block(int start, int end, int maxKey) {this.start = start;this.end = end;this.maxKey = maxKey;}public int getStart() {return start;}public void setStart(int start) {this.start = start;}public int getEnd() {return end;}public void setEnd(int end) {this.end = end;}public int getMaxKey() {return maxKey;}public void setMaxKey(int maxKey) {this.maxKey = maxKey;}
}
相关文章:
Java查找算法练习(2024.7.23)
顺序查找 package SearchExercise20240723; import java.util.Scanner; public class SearchExercise {public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println("需要多大的数组?");int size sc.nextInt();int[] array …...

洗地机哪个牌子好?四款口碑最好的洗地机排名推荐
随着“懒人经济”的出现,越来越多的人开始使用洗地机。洗地机哪个牌子好?为了帮助大家在这个琳琅满目的市场中做出明智决策,本文特别整理了四款口碑最好的洗地机排名推荐,它们凭借出色的清洁效果、智能化的操作体验以及用户的高度…...

如何提升短视频的曝光量和获客效能?云微客来解决
在流量至上的当下,短视频凭借其优势,迅速成为了众多企业获客引流的核心营销手段。进入短视频赛道后,如何提升短视频的曝光量和获客效能,就成为了众多企业亟待解决的焦点。 如果你不想投入大量的广告预算,还想在短视频平…...
SpringBoot开发中如何缓存数据, 减少数据库的访问频率?
一:自定义是否开启缓存 方法一: 在不同环境的配置文件中如application-dev.yml、application-test.yml、application-prod.yml,修改 spring.cache.type none; spring:cache:type: none 方法二: 自定义配置 application.yml&…...
PostgreSQL如何在windows/linux开启归档
linux开启归档: archive_mode onarchive_command test ! -f /mnt/pg12/archivedir/%f && cp %p /mnt/pg12/archivedir/%fwindows开启归档: archive_mode onarchive_command copy "%p" "C:\\server\\pg12\\archivedir\\%f&q…...

【启明智显分享】基于国产Model3芯片的7寸触摸屏助力智慧医疗,电子床头屏提升护理交互
未来医院必然是以信息化为基础,以物联网为特征,以医疗为核心的服务型医院。病房作为医院的重要服务场所,成为智慧医院建设的重要一环。 为提高医护人员与患者的互动交流,给医疗注入智慧元素,让患者享受智能服务&#…...

从理论到实践:如何用 TDengine 打造完美数据模型
在用 TDengine 进行数据建模之前,我们需要回答两个关键问题:建模的目标用户是谁?他们的具体需求是什么?在一个典型的时序数据管理方案中,数据采集和数据应用是两个主要环节。如下图所示: 对于数据采集工程师…...

可以免费合并pdf的软件 合并pdf文件的软件免费 合并pdf的软件免费
在数字化办公的今天,pdf格式因其稳定性和跨平台兼容性被广泛使用。然而,当我们需要将多个 pdf 文件合并为一个时,却往往感到力不从心。本文将为你介绍几款强大的pdf文件合并软件,让你轻松管理文档。 方法一、使用pdf转换器 步骤1…...

【排序 滑动窗口 】1498. 满足条件的子序列数目
本文涉及至知识点 排序 C算法:滑动窗口总结 LeetCode1498. 满足条件的子序列数目 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大,…...
RabbitMQ普通集群搭建指南
RabbitMQ普通集群搭建指南 本文已经完全迁移至,www.geekery.cn 后续不在此更新 目标架构 本次搭建的目标是构建一个由三个节点组成的RabbitMQ集群,节点信息如下: rabbit02: IP地址 192.168.10.132rabbit03: IP地址 192.168.10.133rabbit04:…...

AGV平面坐标系变换公式及实例
1、AGV坐标系简介 如上图,小车前后对角是有激光雷达的,其坐标系称为激光坐标系,采用极坐标系体现。中间为车体坐标系,激光坐标系相对于车体坐标系关系不变;左下角是地图坐标系,小车扫图后,建立的…...
es切片和集群
解决单点故障 支持高并发 解决海量数据 1.cluster 集群:包含多个节点,每个节点属于哪个集群是通过一个集群名称(集群名称,默认是elasticsearch)来决定的,对于中小型应用来说,刚开始一个集群就…...

IEEE官方列表会议 | 第三届能源与环境工程国际会议(CFEEE 2024)
会议简介 Brief Introduction 2024年第三届能源与环境工程国际会议(CFEEE 2024) 会议时间:2024年12月2日-4日 召开地点:澳大利亚凯恩斯 大会官网:CFEEE 2024-2024 International Conference on Frontiers of Energy and Environment Engineer…...

深度学习中的正则化技术 - Dropout篇
序言 在深度学习的浩瀚领域中,模型过拟合一直是研究者们面临的挑战之一。当模型在训练集上表现得近乎完美,却难以在未见过的数据(测试集)上保持同样优异的性能时,过拟合现象便悄然发生。为了有效缓解这一问题…...
《昇思 25 天学习打卡营第 18 天 | 扩散模型(Diffusion Models) 》
《昇思 25 天学习打卡营第 18 天 | 扩散模型(Diffusion Models) 》 活动地址:https://xihe.mindspore.cn/events/mindspore-training-camp 签名:Sam9029 扩散模型(Diffusion Models) 扩散模型概述 扩散模…...

【Django+Vue3 线上教育平台项目实战】Elasticsearch实战指南:从基础到构建课程搜索与数据同步接口
文章目录 前言一、Elasticsearch倒排索引 二、Docker 搭建 ESDocker 安装Docker 搭建 ES 三、ES基础语法创建索引查看索引删除索引添加数据查询数据修改数据删除数据条件查询分页查询排序 多条件查询andor 范围查询 四、ES在项目中的应用示例 前言 在数据驱动的时代,…...

libtins初探-抓包嗅探
libtin 一、概述1. 可移植性2. 特性 二、基础知识1. PDU2. 地址类3. 地址范围类4. 网络接口5. 写pcap文件 三、嗅探1.嗅探基础2. 嗅探器配置3. 循环嗅探4. 使用迭代器嗅探6. 包对象7. 读取pcap文件8. 包的解析 四、发送包1. 发送网络层pdu2. 发送链路层pdu3. 发送和接收响应校验…...

大语言模型-Bert-Bidirectional Encoder Representation from Transformers
一、背景信息: Bert是2018年10月由Google AI研究院提出的一种预训练模型。 主要用于自然语言处理(NLP)任务,特别是机器阅读理、文本分类、序列标注等任务。 BERT的网络架构使用的是多层Transformer结构,有效的解决了长…...

bug诞生记——动态库加载错乱导致程序执行异常
大纲 背景问题发生问题猜测和分析过程是不是编译了本工程中的其他代码是不是有缓存是不是编译了非本工程的文件是不是调用了其他可执行文件查看CMakefiles分析源码检查正在运行程序的动态库 解决方案 这个案例发生在我研究ROS 2的测试Demo时发生的。 整体现象是:修改…...

Matlab演示三维坐标系旋转
function showTwo3DCoordinateSystemsWithAngleDifference() clear all close all % 第一个三维坐标系 origin1 [0 0 0]; x_axis1 [1 0 0]; y_axis1 [0 1 0]; z_axis1 [0 0 1];% 绕 x 轴旋转 30 度的旋转矩阵 theta_x 30 * pi / 180; rotation_matrix_x [1 0 0; 0 cos(th…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...

从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...