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.简体 繁体(台湾)…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
