JAVA练习百题之数组插入元素
题目:有一个已经排好序的数组。现输入一个数,要求按原来的规律将它插入数组中。
程序分析
要将一个数插入已经排好序的数组中,我们可以采用以下步骤:
- 遍历数组,找到第一个大于待插入数的位置。
- 将待插入数插入到该位置,同时将该位置后面的元素依次后移一位。
下面我们将使用三种不同的方法来实现这个任务,并分析它们的优缺点。
方法一:遍历插入
解题思路
我们可以遍历已排序数组,找到第一个大于待插入数的位置,然后将待插入数插入该位置。
实现代码
public class Main {public static void insertSorted(int[] arr, int num) {int i;for (i = 0; i < arr.length; i++) {if (arr[i] > num) {break;}}// 将待插入数插入到位置 i,同时后面的元素后移for (int j = arr.length - 1; j > i; j--) {arr[j] = arr[j - 1];}arr[i] = num;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int num = 4;System.out.print("Original Array: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}insertSorted(arr, num);System.out.print("\nArray after insertion: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}
优缺点
优点:
- 简单易懂,容易实现。
- 对于小规模数组或已经基本有序的数组,性能较好。
缺点:
- 对于大规模数组,性能较差,时间复杂度为O(n)。
方法二:二分查找 + 插入
解题思路
我们可以使用二分查找来快速找到待插入数的位置,然后再进行插入操作。
实现代码
public class Main {public static int binarySearch(int[] arr, int num) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == num) {return mid;} else if (arr[mid] < num) {left = mid + 1;} else {right = mid - 1;}}return left;}public static void insertSorted(int[] arr, int num) {int pos = binarySearch(arr, num);for (int i = arr.length - 1; i >= pos; i--) {arr[i] = arr[i - 1];}arr[pos] = num;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int num = 4;System.out.print("Original Array: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}insertSorted(arr, num);System.out.print("\nArray after insertion: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}
优缺点
优点:
- 较方法一更高效,时间复杂度为O(log n)。
- 适用于大规模数组。
缺点:
- 实现稍微复杂一些。
方法三:使用ArrayList
解题思路
我们可以使用ArrayList来插入新元素,然后再将其转换为数组。
实现代码
import java.util.ArrayList;
import java.util.Arrays;public class Main {public static void insertSorted(ArrayList<Integer> list, int num) {int pos = 0;while (pos < list.size() && list.get(pos) < num) {pos++;}list.add(pos, num);}public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9));int num = 4;System.out.print("Original List: ");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}insertSorted(list, num);System.out.print("\nList after insertion: ");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}}
}
优缺点
优点:
- 使用
ArrayList简化了插入操作。 - 适用于大规模数组。
缺点:
- 需要额外的内存空间来存储
ArrayList。 - 对
ArrayList的插入操作可能稍慢于直接操作数组。
总结
对于小规模数组,方法一或方法三都可以选择,具体取决于个人偏好。方法二在大规模数组中具有更好的性能,因为它的时间复杂度是O(log n),但实现稍微复杂一些。
如果需要处理大规模数组,并且希望保持较高的性能,方法二(二分查找+插入)是一个更好的选择。如果空间使用不是主要考虑因素,也可以考虑方法三(使用ArrayList)。
总的来说,方法二(二分查找+插入)通常是更好的选择,因为它兼顾了性能和实现复杂度。
相关文章:
JAVA练习百题之数组插入元素
题目:有一个已经排好序的数组。现输入一个数,要求按原来的规律将它插入数组中。 程序分析 要将一个数插入已经排好序的数组中,我们可以采用以下步骤: 遍历数组,找到第一个大于待插入数的位置。将待插入数插入到该位…...
C++11常见语法
目录 lambda 表达式 可变模板参数 C11新类的默认函数 包装器 function bind lambda 表达式 lambda 表达式也是可调用对象,在C语言中就有函数指针,但是函数指针比较复杂。 而在C11之前,也有仿函数,使用仿函数,还…...
【数据分析】时间序列
UTC时间:时间戳是以格林威治时间1970年01月01日00时00分00秒为基准计算所经过时间的秒数,是一个浮点数。Python的内置模块time和datetime都可以对时间格式数据进行转换,如时间戳和时间字符串的相互转换。 报错记录:AR has been re…...
【图像算法相关知识点】
【图像算法工程师】 什么是图像处理? 图像处理是指对数字图像进行处理和分析,以达到特定的目的。例如,调整图像的颜色、对比度、亮度等参数,进行图像增强、去噪、分割、特征提取等操作,以及应用计算机视觉算法实现目标…...
竹云筑基,量子加密| 竹云携手国盾量子构建量子身份安全防护体系
9月23日-24日,2023量子产业大会在安徽合肥举行。作为量子科技领域行业盛会,2023年量子产业大会以“协同创新 量点未来”为主题,展示了前沿的量子信息技术、产业创新成果,并举办主旨论坛、量子科普讲座等系列专项活动。量子信息作为…...
数据结构P46(2-1~2-4)
2-1编写算法查找顺序表中值最小的结点,并删除该结点 #include <stdio.h> #include <stdlib.h> typedef int DataType; struct List {int Max;//最大元素 int n;//实际元素个数 DataType *elem;//首地址 }; typedef struct List*SeqList;//顺序表类型定…...
基于BERT模型进行文本处理(Python)
基于BERT模型进行文本处理(Python) 所有程序都由Python使用Spyder运行。 对于BERT,在运行之前,它需要安装一些环境。 首先,打开Spyder。其次,在控制台中单独放置要安装的: pip install transformers pip install tor…...
妙鸭相机功能代码复现
妙鸭相机功能代码复现 妙鸭相机主要实现人脸替换与人脸高清增强修复功能。可通过两种方式实现Roop和Lora模型。 RooP笔记 基础模型:inswapper_128.onnx 人脸分析模型:insightface 高清增强模型:gfpgan 大体流程为通过insightface检测出人脸,替换人脸,使用gfpgan对人…...
使用Java Spring Boot构建高效的爬虫应用
本文将介绍如何使用Java Spring Boot框架来构建高效的爬虫应用程序。通过使用Spring Boot和相关的依赖库,我们可以轻松地编写爬虫代码,并实现对指定网站的数据抓取和处理。本文将详细介绍使用Spring Boot和Jsoup库进行爬虫开发的步骤,并提供一…...
归并排序与非比较排序详解
W...Y的主页 😊 代码仓库分享 💕 🍔前言: 上篇博客我们讲解了非常重要的快速排序,相信大家已经学会了。最后我们再学习一种特殊的排序手法——归并排序。话不多说我们直接上菜。 目录 归并排序 基本思想 递归思路…...
第85步 时间序列建模实战:CNN回归建模
基于WIN10的64位系统演示 一、写在前面 这一期,我们介绍CNN回归。 同样,这里使用这个数据: 《PLoS One》2015年一篇题目为《Comparison of Two Hybrid Models for Forecasting the Incidence of Hemorrhagic Fever with Renal Syndrome i…...
【MATLAB源码-第36期】matlab基于BD,SVD,ZF,MMSE,MF,SLNR预编码的MIMO系统误码率分析。
1、算法描述 1. MIMO (多输入多输出):这是一个无线通信系统中使用的技术,其中有多个发送和接收天线。通过同时发送和接收多个数据流,MIMO可以增加数据速率和系统容量,同时提高信号的可靠性。 2. BD (块对角化):这是一…...
Uniapp 新手专用 抖音登录 获取用户头像、名称、openid、unionid、anonymous_openid、session_key
TC-dylogin 一定请选择 源码授权版 教程 第一步 将代码拷贝至您所需要的页面 该代码位置:pages/index.vue 第二步 修改appid和secret 第三步 获取appid和secret 获取appid和secret链接 注意事项 为了安全,我将默认的自己的appid和secret在云函数中删…...
openssl引擎开发踩坑小记
前言 在开发openssl引擎过程中,引擎莫名其妙的加载不上,错误如下图: 大概意思就是加载引擎动态库时失败了。 在网上一顿搜索后,也没找到想要的答案。 原因 许多引擎都是基于第三方动态库开发的,引擎本身在开发时&a…...
ubuntu 设置x11vnc服务
Ubuntu 18.04 设置x11vnc服务 自带的vino-server也可以用但是不好用,在ubuntu论坛上看见推荐的x11vnc(ubuntu关于vnc的帮助页面),使用设置一下,结果发现有一些坑需要填,所以写下来方便下次使用 转载请说明…...
物理备份xtrabackup
物理备份: 直接复制数据库文件,适用于大型数据库环境,不受存储引擎的限制,但不能恢复到不同的MySQL版本。 1.完全备份-----完整备份: 每次都将所有数据(不管自第一次备份以来有没有修改过)&am…...
1.springcloudalibaba nacos2.2.3部署
前言 nacos是springcloudalibaba体系的注册中心,演示如何搭建最新稳定版本的linux搭建。 前置条件,安装好jdk1.8 一、二进制压缩包下载 1.1 下载压缩包 nacos下载 点击下载下载后得到二进制包如下 nacos-2.2.3.tar.gz二、安装步骤 2.1.解压二进制…...
Linux 查看是否安装memcached
telnet 127.0.0.1 11211这样的命令连接上memcache,然后直接输入stats就可以得到memcache服务器的版本 安装memcached : sudo apt-get install memcached...
设计模式14、命令模式 Command
解释说明:命令模式(Command Pattern)是一种数据驱动的设计模式,它属于行为型模式。请求以命令的形式包裹在对象中,并传递给调用对象。调用对象寻找可以处理该命令的合适对象,并把该命令传给相应的对象&…...
【Go】excelize库实现excel导入导出封装(一),自定义导出样式、隔行背景色、自适应行高、动态导出指定列、动态更改表头
前言 最近在学go操作excel,毕竟在web开发里,操作excel是非常非常常见的。这里我选择用 excelize 库来实现操作excel。 为了方便和通用,我们需要把导入导出进行封装,这样以后就可以很方便的拿来用,或者进行扩展。 我参…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
