当前位置: 首页 > news >正文

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 …...

洗地机哪个牌子好?四款口碑最好的洗地机排名推荐

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

如何提升短视频的曝光量和获客效能?云微客来解决

在流量至上的当下&#xff0c;短视频凭借其优势&#xff0c;迅速成为了众多企业获客引流的核心营销手段。进入短视频赛道后&#xff0c;如何提升短视频的曝光量和获客效能&#xff0c;就成为了众多企业亟待解决的焦点。 如果你不想投入大量的广告预算&#xff0c;还想在短视频平…...

SpringBoot开发中如何缓存数据, 减少数据库的访问频率?

一&#xff1a;自定义是否开启缓存 方法一&#xff1a; 在不同环境的配置文件中如application-dev.yml、application-test.yml、application-prod.yml&#xff0c;修改 spring.cache.type none; spring:cache:type: none 方法二&#xff1a; 自定义配置 application.yml&…...

PostgreSQL如何在windows/linux开启归档

linux开启归档&#xff1a; archive_mode onarchive_command test ! -f /mnt/pg12/archivedir/%f && cp %p /mnt/pg12/archivedir/%fwindows开启归档&#xff1a; archive_mode onarchive_command copy "%p" "C:\\server\\pg12\\archivedir\\%f&q…...

【启明智显分享】基于国产Model3芯片的7寸触摸屏助力智慧医疗,电子床头屏提升护理交互

未来医院必然是以信息化为基础&#xff0c;以物联网为特征&#xff0c;以医疗为核心的服务型医院。病房作为医院的重要服务场所&#xff0c;成为智慧医院建设的重要一环。 为提高医护人员与患者的互动交流&#xff0c;给医疗注入智慧元素&#xff0c;让患者享受智能服务&#…...

从理论到实践:如何用 TDengine 打造完美数据模型​

在用 TDengine 进行数据建模之前&#xff0c;我们需要回答两个关键问题&#xff1a;建模的目标用户是谁&#xff1f;他们的具体需求是什么&#xff1f;在一个典型的时序数据管理方案中&#xff0c;数据采集和数据应用是两个主要环节。如下图所示&#xff1a; 对于数据采集工程师…...

可以免费合并pdf的软件 合并pdf文件的软件免费 合并pdf的软件免费

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

【排序 滑动窗口 】1498. 满足条件的子序列数目

本文涉及至知识点 排序 C算法&#xff1a;滑动窗口总结 LeetCode1498. 满足条件的子序列数目 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大&#xff0c;…...

RabbitMQ普通集群搭建指南

RabbitMQ普通集群搭建指南 本文已经完全迁移至&#xff0c;www.geekery.cn 后续不在此更新 目标架构 本次搭建的目标是构建一个由三个节点组成的RabbitMQ集群&#xff0c;节点信息如下&#xff1a; rabbit02: IP地址 192.168.10.132rabbit03: IP地址 192.168.10.133rabbit04:…...

AGV平面坐标系变换公式及实例

1、AGV坐标系简介 如上图&#xff0c;小车前后对角是有激光雷达的&#xff0c;其坐标系称为激光坐标系&#xff0c;采用极坐标系体现。中间为车体坐标系&#xff0c;激光坐标系相对于车体坐标系关系不变&#xff1b;左下角是地图坐标系&#xff0c;小车扫图后&#xff0c;建立的…...

es切片和集群

解决单点故障 支持高并发 解决海量数据 1.cluster 集群&#xff1a;包含多个节点&#xff0c;每个节点属于哪个集群是通过一个集群名称&#xff08;集群名称&#xff0c;默认是elasticsearch&#xff09;来决定的&#xff0c;对于中小型应用来说&#xff0c;刚开始一个集群就…...

IEEE官方列表会议 | 第三届能源与环境工程国际会议(CFEEE 2024)

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

深度学习中的正则化技术 - Dropout篇

序言 在深度学习的浩瀚领域中&#xff0c;模型过拟合一直是研究者们面临的挑战之一。当模型在训练集上表现得近乎完美&#xff0c;却难以在未见过的数据&#xff08;测试集&#xff09;上保持同样优异的性能时&#xff0c;过拟合现象便悄然发生。为了有效缓解这一问题&#xf…...

《昇思 25 天学习打卡营第 18 天 | 扩散模型(Diffusion Models) 》

《昇思 25 天学习打卡营第 18 天 | 扩散模型&#xff08;Diffusion Models&#xff09; 》 活动地址&#xff1a;https://xihe.mindspore.cn/events/mindspore-training-camp 签名&#xff1a;Sam9029 扩散模型&#xff08;Diffusion Models&#xff09; 扩散模型概述 扩散模…...

【Django+Vue3 线上教育平台项目实战】Elasticsearch实战指南:从基础到构建课程搜索与数据同步接口

文章目录 前言一、Elasticsearch倒排索引 二、Docker 搭建 ESDocker 安装Docker 搭建 ES 三、ES基础语法创建索引查看索引删除索引添加数据查询数据修改数据删除数据条件查询分页查询排序 多条件查询andor 范围查询 四、ES在项目中的应用示例 前言 在数据驱动的时代&#xff0c…...

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

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

bug诞生记——动态库加载错乱导致程序执行异常

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

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…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...