当前位置: 首页 > 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…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

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

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

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

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

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...