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。 为了方便和通用,我们需要把导入导出进行封装,这样以后就可以很方便的拿来用,或者进行扩展。 我参…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
comfyui 工作流中 图生视频 如何增加视频的长度到5秒
comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗? 在ComfyUI中实现图生视频并延长到5秒,需要结合多个扩展和技巧。以下是完整解决方案: 核心工作流配置(24fps下5秒120帧) #mermaid-svg-yP…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
