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

【C语言】【Leetcode】88. 合并两个有序数组

文章目录

  • 一、题目
  • 二、思路
  • 再思考


一、题目

链接: link

在这里插入图片描述


二、思路

这题属于简单题,比较粗暴的做法就是直接比较两个数组,先把第二个数组加到第一个的后面,如何冒泡排序,这种方法简单粗暴但有效,可是不适用于这题,这题要求我们控制时间复杂度在O(m+n)里所以我们可以尝试双指针的方法

但是这里还是用qsort函数的方法给大家写一下,这种函数的内置排序算法与冒泡类似,大家有兴趣可以看一下链接: link

里面的排序过程大致如下

void bubble(void* base, int count, int size, int(*cmp)(void*, void*))
{for (int i = 0; i < count - 1; i++){for (int j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){_swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}

然后是整个程序的编写过程

int cmp(int* a, int* b) {return *a - *b;
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i = 0; i != n; ++i) {nums1[m + i] = nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}

在这里插入图片描述
双指针,顾名思义,设立 两个指针锁定两个指针的索引 进行比较,小的数放入一个新创立的数组,最后再把这个新创立的数组的值赋给num1就行了

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int nums[nums1Size];int p1 = 0;int p2 = 0;int tmp; // 用来临时记录当前值while (p1 < m || p2 < n) {if (p1 == m)tmp = nums2[p2++];else if (p2 == n)tmp = nums1[p1++];else if (nums1[p1] > nums2[p2])tmp = nums2[p2++];elsetmp = nums1[p1++];nums[p1 + p2 - 1] = tmp;}for (int i = 0; i < m + n; i++) {nums1[i] = nums[i];}
}

再思考

如何不创立新的数组进行排序呢

如果是上一种方法,我们虽然时间复杂度小了下去,变成了O(m+n)但是同时创立了个数组,所以空间复杂度也变成了O(m+n)

为了不多创建一个新的数组,我们可以利用num1数组后面多出来的那几个0做文章,我们在上一种方法中采用的是先把小的取出来,但是如果我们先把大的取出来,放进num1数组的末尾,这样再不创建新的数组的前提下,num1数组的元素也不会被覆盖了

代码如下

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = m - 1, p2 = n - 1;int tail = m + n - 1;int cur;while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {cur = nums2[p2--];} else if (p2 == -1) {cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];} else {cur = nums2[p2--];}nums1[tail--] = cur;}
}

相关文章:

【C语言】【Leetcode】88. 合并两个有序数组

文章目录 一、题目二、思路再思考 一、题目 链接: link 二、思路 这题属于简单题&#xff0c;比较粗暴的做法就是直接比较两个数组&#xff0c;先把第二个数组加到第一个的后面&#xff0c;如何冒泡排序&#xff0c;这种方法简单粗暴但有效&#xff0c;可是不适用于这题&…...

DMA控制器

前言 大家好&#xff0c;我是jiantaoyab&#xff0c;这是我作为学习笔记的25篇&#xff0c;本篇文章给大家介绍DMA。 无论 I/O 速度如何提升&#xff0c;比起 CPU&#xff0c;总还是太慢。如果我们对于 I/O 的操作&#xff0c;都是由 CPU 发出对应的指令&#xff0c;然后等待…...

SQLiteC/C++接口详细介绍sqlite3_stmt类(十)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍sqlite3_stmt类&#xff08;九&#xff09; 下一篇&#xff1a; SQLiteC/C接口详细介绍sqlite3_stmt类&#xff08;十一&#xff09; 38、sqlite3_column_value sqlite3_column_valu…...

Android 生成Excel文件保存到本地

本文用来记录在安卓中生成Excel文件并保存到本地操作&#xff0c;在网上找了好久&#xff0c;终于找到一个可以用的&#xff0c;虽然代码已经很老的&#xff0c;但亲测可用&#xff01; 项目地址&#xff1a;https://github.com/wanganan/AndroidExcel 可以下载下来修改直接用…...

Hive-技术补充-ANTLR语法编写

一、导读 我们学习一门语言&#xff0c;或外语或编程语言&#xff0c;是不是都是要先学语法&#xff0c;想想这些语言有哪些相同点 1、中文、英语、日语......是不是都有 主谓宾 的规则 2、c、java、python、js......是不是都有 数据类型 、循环 等语法或数据结构 虽然人们在…...

6.使用个人用户登录域控的成员服务器,如何防止个人用户账号的用户策略生效?

&#xff08;1&#xff09;需求&#xff1a; &#xff08;2&#xff09;实战配置步骤 第一步:创建新的策略-并编辑策略 第二步&#xff1a;将策略应用到服务器处在OU 第三步&#xff1a;测试 &#xff08;1&#xff09;需求&#xff1a; 比如域控&#xff0c;或者加入域的…...

模拟算法

例题一 算法思路&#xff1a; 纯模拟。从前往后遍历整个字符串&#xff0c;找到问号之后&#xff0c;就⽤ a ~ z 的每⼀个字符去尝试替换即 可。 例题二 解法&#xff08;模拟 分情况讨论&#xff09;&#xff1a; 算法思路&#xff1a; 模拟 分情况讨论。 计算相邻两个…...

【数据结构刷题专题】—— 二叉树

二叉树 二叉树刷题框架 二叉树的定义&#xff1a; struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL); };1 二叉树的遍历方式 【1】前序遍历 class Solution { public:void traversal(TreeNode* node, vector&…...

基于AWS云服务构建智能家居系统的最佳实践

在当今智能家居时代,构建一个安全、高性能、可扩展和灵活的智能家居系统已经成为许多公司的目标。亚马逊网络服务(AWS)提供了一系列云服务,可以帮助企业轻松构建和管理智能家居系统。本文将探讨如何利用AWS云服务构建一个智能家居系统,并分享相关的最佳实践。 系统架构概述 该…...

Java零基础-集合:Set接口

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一个人虽可以走的更快&#xff0c;但一群人可以走的更远。 我是一名后…...

数据结构与算法-排序算法

1.顺序查找 def linear_search(iters, val):for i, v in enumerate(iters):if v val:return ireturn 2.二分查找 # 升序的二分查找 def binary_search(iters, val):left 0right len(iters)-1while left < right:mid (left right) // 2if iters[mid] val:return mid…...

SpringBoot 文件上传(三)

之前讲解了如何接收文件以及如何保存到服务端的本地磁盘中&#xff1a; SpringBoot 文件上传&#xff08;一)-CSDN博客 SpringBoot 文件上传&#xff08;二&#xff09;-CSDN博客 这节讲解如何利用阿里云提供的OSS&#xff08;Object Storage Service)对象存储服务保存文件。…...

web渗透测试漏洞流程:红队目标信息收集之资产搜索引擎收集

web渗透测试漏洞流程 渗透测试信息收集---域名信息收集1.域名信息的科普1.1 域名的概念1.2 后缀分类1.3 多重域名的关系1.4 域名收集的作用1.5 DNS解析原理1.6 域名解析记录2. 域名信息的收集的方法2.1 基础方法-搜索引擎语法2.1.1 Google搜索引擎2.1.1.1 Google语法的基本使用…...

UI自动化_id 元素定位

## 导包selenium from selenium import webdriver import time1、创建浏览器驱动对象 driver webdriver.Chrome() 2、打开测试网站 driver.get("你公司的平台地址") 3、使浏览器窗口最大化 driver.maximize_window() 4、在用户名输入框中输入admin driver.find_ele…...

华为OD技术面算法题整理

LeetCode原题 简单 题目编号频次409. 最长回文串 - 力扣(LeetCode)3...

vmware虚拟机下ubuntu扩大磁盘容量

1、扩容&#xff1a; 可以直接在ubuntu setting界面里直接扩容&#xff0c;也可通过vmware命令&#xff0c;如下&#xff1a; vmware提供一个命令行工具&#xff0c;vmware-vdiskmanager.exe&#xff0c;位于vmware的安装目录下&#xff0c;比如 C:/Program Files/VMware/VMwar…...

秋招打卡算法题第一天

一年多没有刷过算法题了&#xff0c;已经不打算找计算机类工作了&#xff0c;但是思来想去&#xff0c;还是继续找吧。 1. 字符串最后一个单词的长度 public static void main(String[] args) {Scanner in new Scanner(System.in);while(in.hasNextInt()){String itemin.nextL…...

BC98 序列中删除指定数字

题目 描述 有一个整数序列&#xff08;可能有重复的整数&#xff09;&#xff0c;现删除指定的某一个整数&#xff0c;输出删除指定数字之后的序列&#xff0c;序列中未被删除数字的前后位置没有发生改变。 数据范围&#xff1a;序列长度和序列中的值都满足 1≤&#xfffd;≤…...

基于Java的学生体质健康管理系统的设计与实现(论文+源码)_kaic

摘 要 随着时代的进步&#xff0c;信息化也在逐渐深入融进我们生活的方方面面。其中也给健康管理带来了新的发展方向。通过对学生体质健康管理的研究与分析发现当下的管理系统还不够全面&#xff0c;系统的性能达不到使用者的要求。因此&#xff0c;本文结合Java的优势和流行性…...

【Linux系统】冯诺依曼与操作系统

什么是冯诺依曼体系结构&#xff1f; 如图即为冯诺依曼大致的体系结构图&#xff0c; 我们知道这些都是由我们的计算机硬件组成 输入设备&#xff1a;键盘&#xff0c; 鼠标&#xff0c; 摄像头&#xff0c; 话筒&#xff0c; 磁盘&#xff0c; 网卡... 输出设备&#xff1a…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...