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

【在一个升序数组中插入一个数仍升序输出】

在一个升序数组中插入一个数仍升序输出

题目举例:

有一个升序数组nums,给一个数字data,将data插入数组nums中仍旧保证nums升序,返回数组中有效元素个数。
比如:nums[100] = {1, 2, 3, 5, 6, 7, 8, 9} size = 8 data = 4
插入之后,nums为{1, 2, 3, 4, 5, 6, 7, 8, 9}
返回 size = 9

方法一:插入排序

1.1方法解析

1.遍历数组nums,找到第一个大于等于data的元素位置index。
2.将index及其之后的元素都往后移动一位,腾出位置给数据。
3.将data插入到index位置。
4.size加1。

1.2函数实现

int insertIntoArray(int nums[], int size, int data) {int i, index;// 找到第一个大于等于data的元素位置for (i = 0; i < size; i++) {if (nums[i] >= data) {index = i;break;}}// 将index及其之后的元素都往后移动一位for (i = size - 1; i >= index; i--) {nums[i + 1] = nums[i];}// 将data插入到index位置nums[index] = data;// size加1size++;

1.3实际代入

void insertIntoArray(int nums[], int size, int data) {int i, index;// 找到第一个大于等于data的元素位置for (i = 0; i < size; i++) {if (nums[i] >= data) {index = i;break;}}// 将index及其之后的元素都往后移动一位for (i = size - 1; i >= index; i--) {nums[i + 1] = nums[i];}// 将data插入到index位置nums[index] = data;// size加1size++;
for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\n");printf("size = %d", size);
}
int main()
{int nums[100] = { 1,2,3,5,6,7,8,9 };int size = 8;printf("插入前:");for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\nsize = %d\n", size);int data = 0;scanf("%d", &data);printf("插入后:");Inserdata(nums, size, data);return 0;}

1.4运行结果举例

在这里插入图片描述

方法二 :二分查找插入排序

2.1方法解析

首先,初始化两个指针和分别指向数组的起始和结束位置。然后进行循环,直到大于等于为止。在每一次循环中,计算中间位置,并将中间元素与要插入的值进行比较。leftrightleftrightmid
如果中间元素大于要插入的值,说明要插入的值在左半部分,将指针更新为;
如果中间元素小于要插入的值,说明要插入的值在右半部分,将指针更新为;
如果中间元素等于要插入的值,说明要插入的值已rightmid-1leftmid+1
最终,当大于时,并将要插入的值放入该位置即可。返回数组大小加1。leftright

2.2函数实现

void Inserdata(int nums[], int size, int data)  //方法二:二分法查找插入排序
{int left = 0;int right = size - 1;while (left < right){int mid = (left + right) / 2;int midvalue = nums[mid];if (nums[mid] < data)//找到中间数和data对比{left = mid + 1;}else{right = mid - 1;}}for (int i = size - 1; i >= left; i--){nums[i + 1] = nums[i];}nums[left] = data;size++;for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\n");printf("size = %d", size);
}

2.3实际代入

void Inserdata(int nums[], int size, int data)  //方法二:二分法查找插入排序
{int left = 0;int right = size - 1;while (left < right){int mid = (left + right) / 2;int midvalue = nums[mid];if (nums[mid] < data){left = mid + 1;}else{right = mid - 1;}}for (int i = size - 1; i >= left; i--){nums[i + 1] = nums[i];}nums[left] = data;size++;for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\n");printf("size = %d", size);
}
int main()
{int nums[100] = { 1,2,3,5,6,7,8,9 };int size = 8;printf("插入前:");for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\nsize = %d\n", size);int data = 0;scanf("%d", &data);printf("插入后:");Inserdata(nums, size, data);return 0;
}

2.4运行结果举例

在这里插入图片描述

方法三 依次次对比

3.1方法解析

1.数组为升序
2在数组中找待插入元素的位置,具体找的方式为
3.从后往前依次与数组中元素进行比较,如果要插入元素num比end位置数据小,则num一定插在end位置之前
4.因此将end位置数据往后搬移一个位置
5.如果num大于end位置元素或者end已经在区间最左侧,则位置找到/ 最后将新元素插入到end+1的位置

3.2函数实现

void Inserdata(int nums[], int size, int data)  //方法三:依次对比
{int end = size - 1;while (end >= 0 && data < nums[end]){nums[end + 1] = nums[end];end--;}nums[end + 1] = data;// 返回插入之后,数组中有效元素个数size++;for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\n");printf("size = %d", size);
}

3.3实际代入

void Inserdata(int nums[], int size, int data)  //方法三:依次对比
{int end = size - 1;while (end >= 0 && data < nums[end]){nums[end + 1] = nums[end];end--;}nums[end + 1] = data;// 返回插入之后,数组中有效元素个数size++;for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\n");printf("size = %d", size);
}
int main()
{int nums[100] = { 1,2,3,5,6,7,8,9 };int size = 8;printf("插入前:");for (int i = 0; i < size; i++){printf("%d ", nums[i]);}printf("\nsize = %d\n", size);int data = 0;scanf("%d", &data);printf("插入后:");Inserdata(nums, size, data);return 0;
}

3.4运行结果举例

在这里插入图片描述

相关文章:

【在一个升序数组中插入一个数仍升序输出】

在一个升序数组中插入一个数仍升序输出 题目举例&#xff1a; 有一个升序数组nums&#xff0c;给一个数字data&#xff0c;将data插入数组nums中仍旧保证nums升序&#xff0c;返回数组中有效元素个数。 比如&#xff1a;nums[100] {1, 2, 3, 5, 6, 7, 8, 9} size 8 data 4 …...

图像去雨、去雪、去雾论文学习记录

All_in_One_Bad_Weather_Removal_Using_Architectural_Search 这篇论文发表于CVPR2020&#xff0c;提出一种可以应对多种恶劣天气的去噪模型&#xff0c;可以同时进行去雨、去雪、去雾操作。但该部分代码似乎没有开源。 提出的问题&#xff1a; 当下的模型只能针对一种恶劣天气…...

YARN框架和其工作原理流程介绍

目录 一、YARN简介 二、YARN的由来 三、YARN的基本设计思想 四、YARN 的基本架构 4.1 基本架构图 4.2 基本组件介绍 4.2.1 ResourceManager 4.2.1.1 任务调度器(Resource Scheduler) 4.2.1.2 应用程序管理器&#xff08;Applications Manager&#xff09; 4.2.1.3 其他…...

多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测

多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测 目录 多维时序 | MATLAB实现ZOA-CNN-BiGRU-Attention多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.Matlab基于ZOA-CNN-BiGRU-Attention斑马优化卷积双向门控循环单元网络…...

centos上下载redis

1.redis 特点 Redis特性&#xff08;8个&#xff09; 1 速度快&#xff1a;10w ops&#xff08;每秒10w读写&#xff09;&#xff0c;数据存在内存中&#xff0c;c语言实现&#xff0c;单线程模型 2 持久化&#xff1a;rdb和aof 3 多种数据结构&#xff1a; 5大数据结构 …...

黑马项目一阶段面试58题 Web14题(二)

八、内连接和外连接查询有什么区别 内连接 获取两表的交集部分 外连接 获取某表的所有数据&#xff0c;以及两表的交集数据 九、事务管理的作用&#xff0c;四大特性 作用 保证多个增删改的操作&#xff0c;要么同时成功&#xff0c;要么同时失败 四大特性 1.原子性 事…...

软考高项-思维导图34-36(计算机高级系统项目管理师)

陆续更新一些软考高项的思维导图&#xff0c;都是一些必背知识点&#xff0c;希望可以帮助大家早日考过高项&#xff0c;早日当上高工&#xff0c;早日成为杭州E类人才。全部完整导图快速获取链接&#xff1a;计算机高级系统项目管理师-思维导图汇总 三十四、需求按层次分 三十…...

C++的stack和queue+优先队列

文章目录 什么是容器适配器底层逻辑为什么选择deque作为stack和queue的底层默认容器优先队列优先队列的模拟实现stack和queue的模拟实现 什么是容器适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)&#xff0c;…...

Ubuntu 18.04.6 Android Studio Giraffe adb logcat 无法使用

在 Ubuntu 18.04.6 上 在链接上设备以后&#xff0c;发现可以用 Android Studio 安装应用 但无法用 Android Studio 看 logcat 手动从命令行停止&#xff0c;启动 adb 会报错如下: daemon not running. starting it now on port 5037 ADB server didnt ACK fail…...

Python采集天气数据,做可视化分析【附源码】

嗨害大家好鸭&#xff01;我是小熊猫~ 毕业设计大家着急吗&#xff1f; 没事&#xff0c;我来替大家着急 源码、素材python永久安装包:点击此处跳转文末名片获取 本文知识点: 动态数据抓包 requests发送请求 结构化非结构化数据解析 开发环境: python 3.8 运行代码 pycharm 2…...

优维低代码实践:自定义模板

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…...

电商3D产品渲染简明教程

3D 渲染让动作电影看起来更酷&#xff0c;让建筑设计变得栩栩如生&#xff0c;现在还可以帮助营销人员推广他们的产品。 从最新的《阿凡达》电影到 Spotify 的上一次营销活动&#xff0c;3D 的应用让一切变得更加美好。 在营销领域&#xff0c;3D 产品渲染可帮助品牌创建产品的…...

探索未来:元宇宙与Web3的无限可能

随着科技的奇迹般发展&#xff0c;互联网已经成为了我们生活的不可分割的一部分。然而&#xff0c;尽管它的便利性和普及性带来了巨大的影响&#xff0c;但我们仍然面临着传统互联网体验的诸多限制。 购物需要不断在实体店与电商平台间切换&#xff0c;教育依然受制于时间与地…...

GraphQL(六)登录态校验Directive

GraphQL Directive&#xff08;指令&#xff09;是GraphQL中的一种特殊类型&#xff0c;它允许开发者在GraphQL schema中添加元数据&#xff0c;以控制查询和解析操作的行为 Directive的详细说明及使用可见GraphQL&#xff08;五&#xff09;指令[Directive]详解 本文将介绍通过…...

强大的AI语言模型

1.kameAI 点我 1️⃣可以绘图 2️⃣对接4.0 3️⃣具有长篇写作...

成集云 | 鼎捷ERP采购单同步钉钉 | 解决方案

源系统成集云目标系统 方案介绍 鼎捷ERP&#xff08;Enterprise Resource Planning&#xff09;是一款综合性的企业管理软件&#xff0c;它包括了多个模块来管理企业的各个方面&#xff0c;其中之一就是采购订单模块。鼎捷ERP的采购订单模块可以帮助企业有效管理和控制采购过程…...

【Kubernetes】Kubernetes的PV和PVC的用法

PV、PVC 前言一、 存储卷1. emptyDir 存储卷1.1 概念1.2 实例 2. hostPath 存储卷2.1 概念2.2 实例 3. nfs共享存储卷 二、PV 和 PVC1. 概念1.1 PV1.2 PVC1.3 PVC 的使用逻辑1.4 创建机制1.5 PV 和 PVC 的生命力周期1.6 创建及销毁 PV 的流程 2. PV 和 PVC 的创建2.1 查看定义2…...

【Redis】Redis三种集群模式-主从、哨兵、集群各自架构的优点和缺点对比

文章目录 前言1. 单机模式2. 主从架构3. 哨兵4. 集群模式总结 前言 如果Redis的读写请求量很大&#xff0c;那么单个实例很有可能承担不了这么大的请求量&#xff0c;如何提高Redis的性能呢&#xff1f;你也许已经想到了&#xff0c;可以部署多个副本节点&#xff0c;业务采用…...

Python爬虫:如何使用Python爬取网站数据

更新&#xff1a;2023-08-13 15:30 想要获取网站的数据&#xff1f;使用Python爬虫是一个绝佳的选择。Python爬虫是通过自动化程序来提取互联网上的信息。本文章将会详细介绍Python爬虫的相关技术。 一、网络协议和请求 在使用Python爬虫之前&#xff0c;我们需要理解网络协…...

剑指offer专题2:队列和栈

用两个栈模拟队列 class CQueue {stack<int> stack1;stack<int> stack2; public:CQueue() {}void appendTail(int value) {stack1.push(value);}int deleteHead() {int val-1;if(!stack2.empty()){val stack2.top();stack2.pop();}else if(!stack1.empty()){while…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

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

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

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

6.计算机网络核心知识点精要手册

计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法&#xff1a;数据与控制信息的结构或格式&#xff0c;如同语言中的语法规则语义&#xff1a;控制信息的具体含义和响应方式&#xff0c;规定通信双方"说什么"同步&#xff1a;事件执行的顺序与时序…...