912.排序数组(归并排序)
目录
- 题目
- 解法
- 初始数组
- 1. 分解阶段
- 2. 合并阶段
- 结果
- 为什么要创建长整型
- ll mid = l + ((r - l) >> 1);其中的>>是什么意思
题目
给你一个整数数组 nums,请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。
解法
typedef long long ll;
const int N = 1e5 + 1;
class Solution {ll help[N];void merge(vector<int>& nums, ll l, ll r) {//1、将数组排序if (l >= r) return;ll mid = l + ((r - l) >> 1);ll i = l, j = mid + 1, t = l;while (i <= mid && j <= r) {help[t++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];}//2、将左半区域剩余元素排序while (i <= mid) {help[t++] = nums[i++];}//3、将右半区域剩余元素排序while (j <= r) {help[t++] = nums[j++];}//4、复制数组for (int i = l; i <= r; i++) {nums[i] = help[i];}return;}void mergeSort(vector<int>& nums, ll l, ll r) {if (l < r) {ll mid = l + ((r - l) >> 1);//左边区域mergeSort(nums, l, mid);//右边区域mergeSort(nums, mid + 1, r);//合并左右区域merge(nums, l, r);}}public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();mergeSort(nums, 0, n - 1);return nums;}
};
好的,下面我将详细展示使用归并排序的过程,以数组 nums = {38, 27, 43, 3, 9, 82, 10} 为例。
初始数组
nums = {38, 27, 43, 3, 9, 82, 10}
1. 分解阶段
归并排序首先将数组分解成子数组,直到每个子数组只包含一个元素。
-
初始分解:
{38, 27, 43, 3, 9, 82, 10} -
继续分解:
{38, 27, 43} {3, 9, 82, 10} -
再次分解:
{38} {27, 43} {3, 9} {82, 10} -
继续分解:
{38} {27} {43} {3} {9} {82} {10}
2. 合并阶段
接下来开始合并和排序:
-
合并
{27}和{43}:{27, 43} -
合并
{27, 43}和{38}:{27, 38, 43} -
合并
{3}和{9}:{3, 9} -
合并
{82}和{10}:{10, 82} -
合并
{3, 9}和{10, 82}:{3, 9, 10, 82} -
最后合并
{27, 38, 43}和{3, 9, 10, 82}:{3, 9, 10, 27, 38, 43, 82}
结果
经过归并排序后,数组 nums 最终变为:
nums = {3, 9, 10, 27, 38, 43, 82}
为什么要创建长整型
typedef long long ll;:这行代码为 long long 类型创建了一个别名 ll。这样,在后续的代码中,你可以使用 ll 来代替 long long,使代码更简洁易读。
const int N = 1e5 + 1;:这行代码定义了一个常量 N,其值为 100001。通常在算法中,N 可能用于表示数组的最大大小或某种限制,以确保在使用时不会越界。
在 C++ 中,创建 long long 类型的原因主要是为了处理更大的整数范围。long long 通常用于存储可能超出 int 范围的数值,特别是在涉及到大数运算、数组索引、计数或求和时。以下是一些具体的原因:
-
数值范围:
int的范围通常是 -2,147,483,648 到 2,147,483,647,而long long的范围可以达到 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807,适合处理更大的数值。 -
避免溢出:在进行大量累加、乘法等运算时,如果使用
int,可能会出现溢出错误。使用long long可以降低这种风险。 -
算法需要:在一些算法(如动态规划、图算法等)中,可能需要处理大量数据或计算结果,使用
long long确保结果不会溢出。
因此,在需要处理较大整数的情况下,使用 long long 是一种常见的做法。
ll mid = l + ((r - l) >> 1);其中的>>是什么意思
“”>> 是位移运算符,表示右移操作。在这个表达式中,(r - l) >> 1 相当于将 (r - l) 的值除以 2,用于计算中间值 mid,以提高效率。
相关文章:
912.排序数组(归并排序)
目录 题目解法初始数组1. 分解阶段2. 合并阶段结果 为什么要创建长整型ll mid l ((r - l) >> 1);其中的>>是什么意思 题目 给你一个整数数组 nums,请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O…...
使用 cmake 在 x86 系统中为 arm 系统交叉编译程序
原理: 在 x86 系统里使用交叉编译工具链(arm 版 gcc/g)编译程序,然后放在 arm 系统里运行。 arm 版本 使用 lscpu 查看 cpu 架构 版本说明armv732 bitarmv8/arrch6464 bit 安装交叉编译工具链 # 针对 armv7 sudo apt install…...
软考(网工)——网络规划设计
文章目录 🕐综合布线1️⃣结构化布线系统2️⃣综合布线六大子系统3️⃣综合布线物理结构图 🕑网络分析与设计1️⃣网络规划设计模型2️⃣网络流量分析3️⃣网络安全技术措施表4️⃣技术评价 🕒网络结构与功能1️⃣局域网结构类型2️⃣三层架构…...
即插即用特征融合模块,即用即涨点!
特征融合(Feature Fusion)是深度学习中的一种重要技术,它可以帮助模型更好地理解数据的内在结构和规律,提高模型的性能和泛化能力。 另外,特征融合还可以提高模型的分类准确率,减少过拟合风险,…...
蓝桥算法双周赛 第 19 场 小白入门赛
打开石门 只要有相连的一样字母就可以消成一个 string s; int ans;void solve() {cin >> s;int len 0;for (int i 0;i < s.size();i ){if (s[i] L) len ;else //遇到Q{ans (len ? 1 : 0); //消除累计的Llen 0;ans ;//遇到Q}}//QLLLL时,最后遇不到Q让累计的L消…...
Cursor零基础小白教程系列「进阶」 - Cursor 智能代码补全详解(Tab)
最适合小白零基础的Cursor教程 网站lookai.top相同作者,最新文章会在网站更新,欢迎收藏书签 Cursor 智能代码补全详解(Tab) 概述 Cursor的智能代码补全,也就是快捷键Tab,是其最强大和独特的AI辅助编程工具之一。本教程将详细介绍…...
数据结构《顺序表》
文章目录 前言一、什么是顺序表?1.1 顺序表的概念1.2 顺序表的建立 二、MyArrayList的实现三、顺序表的方法四、关于顺序表的例子总结 前言 提示:这里涉及到的ArrayList类是一个泛型类,同时后面的很多内容都会涉及到泛型,如果不了…...
视频分享网站毕业设计基于SpringBootSSM框架
目录 1.摘要 2.引言 2.1 研究意义 3 功能描述 3.1功能图展示 3.2非功能需求 4. 需求分析 4.1前端技术 4.2后端技术 4.3视频处理技术 4.4内容分发网络(CDN) 4.5其他关键技术 计算机毕业设计/springboot/javaWEB/J2EE/MYSQL数据库/vue前后…...
Python多进程学习与使用:全面指南
Python多进程学习与使用:全面指南 目录 引言什么是多进程?为什么使用多进程?Python中的多进程模块:multiprocessing创建进程的基本方法进程间通信进程池多进程与多线程的比较常见问题和解决方案最佳实践和性能优化实战项目&…...
HTTP Proxy环境下部署Microsoft Entra Connect和Health Agents
在企业环境中,时常需要通过使用HTTP Proxy访问Internet,在使用HTTP Proxy访问Internet的环境中部署Microsoft Entra Connect和Microsoft Entra Connect Health Agents可能会遇到一些额外的配置步骤,以便这些服务能够正常连接到Internet。 一…...
基于单片机的 OLED 显示终端设计分析与研究
摘要: 我国的经济发展速度正在不断加快,经济体制也在经历着一系列的改革,工业发展也正是受到了它的影响,逐步发生变化。在这样的背景下,传统的 LCD 显示技术,逐渐被显示效果更好,功耗更低的 OLED 代替。本文主要介绍了基于单片机的 OLED 显示终端设计,该设计目前具有很…...
基于Multisim压力报警器电路设计(含仿真和报告)
【全套资料.zip】压力报警器电路设计Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 压力报警器包括:压力检测、信号放大、声光报警当电路检测到系统压力正常时,不进行声、光报…...
基于Springboot的在线考试与学习交流平台的设计与实现
基于Springboot的在线考试与学习交流平台 开发语言:Java 框架:springboot JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:idea 源码获取:https://download.csdn.net/downlo…...
“避免序列化灾难:掌握实现 Serializable 的真相!(二)”
文章目录 一、什么是序列化?二、Serializable 是如何起作用的?三、为什么不自动序列化所有对象?四、Java 序列化的底层原理序列化的核心步骤: 五、反序列化的原理六、总结:为什么必须实现 Serializable 才能序列化&…...
中国工商银行智能运维体系建设
随着信息技术的快速发展,分布式架构已经成为主流的系统架构形式。基于分布式架构的系统具有资源利用率高、可扩展性好等优点,已广泛应用于各类企业信息系统之中。分布式监控系统应运而生,它通过在各个节点部署轻量级代理程序,实现对分布式系统的监控数据采集和分析,有效地解决…...
如何将logism电路转为verilog(一)
好长时间没写博客了 下文中提到的文件可在此仓库下载:https://github.com/deadfffool/HUST-Computer-Organization-Big-Homework/tree/main 在转换为verilog之前,需要对logisim电路做以下几点改动: 首先将下载的logisim_change.jar放在与log…...
【论文笔记】X-Former: Unifying Contrastive and Reconstruction Learning for MLLMs
🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。 基本信息 标题: X-Former: Unifying Contr…...
带权并查集注意事项
食物链 #include<bits/stdc.h> using namespace std; const int N5e410; int p[N],d[N]; int find(int x) {if(p[x]!x){int rootfind(p[x]);d[x]d[p[x]];p[x]root;}return p[x]; } int main() {int n,k;cin>>n>>k;for(int i1;i<n;i)p[i]i;int ans0;while…...
No.18 笔记 | XXE(XML 外部实体注入)漏洞原理、分类、利用及防御整理
一、XXE 漏洞概述 (一)定义 XXE(XML 外部实体注入)漏洞源于 XML 解析器对外部实体的不当处理,攻击者借此注入恶意 XML 实体,可实现敏感文件读取、远程命令执行和内网渗透等危险操作。 (二&am…...
Discuz | 全站多国语言翻译和繁体本地转换插件 特色与介绍
Discuz全站多国语言翻译和繁体本地转换插件 特色与介绍 特殊:集成了2个开源库1.多国语言翻译 来自:github.com/xnx3/translate特色:无限使用接口 免费使用2个翻译端 带有一级和二级缓存 实现秒翻译 2.简体 繁体(台湾)…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
