AcWing 787. 归并排序——算法基础课题解
AcWing 787. 归并排序
文章目录
- 题目描述
- C++
- Go
- 模板
题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼10^9 范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
C++
#include <iostream>using namespace std;const int N = 1e5 + 10;int tmp[N];void merge_sort(int q[], int l, int r) {if (l >= r) return;int mid = (l + r) >> 1;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r) {if (q[i] <= q[j]) tmp[k++] = q[i++];else tmp[k++] = q[j++];}while (i <= mid) tmp[k++] = q[i++];while (j <= r) tmp[k++] = q[j++];for (i = l; i <= r; i++) q[i] = tmp[i - l];
}int main() {int n;cin >> n;int q[N];for (int i = 0; i < n; i++) cin >> q[i];merge_sort(q, 0, n - 1);for (int i = 0; i < n; i++) cout << q[i] << " ";return 0;
}
Go
package mainimport "fmt"const N = 1e5 + 10var tmp = make([]int, N)func mergeSort(arr []int, l, r int) {if l >= r {return}mid := (l + r) >> 1mergeSort(arr, l, mid)mergeSort(arr, mid+1, r)k := 0i := lj := mid + 1for i <= mid && j <= r {if arr[i] <= arr[j] {tmp[k] = arr[i]i++} else {tmp[k] = arr[j]j++}k++}for i <= mid {tmp[k] = arr[i]i++k++}for j <= r {tmp[k] = arr[j]j++k++}for i := l; i <= r; i++ {arr[i] = tmp[i-l]}
}func main() {var n intfmt.Scanf("%d", &n)arr := make([]int, N)for i := 0; i < n; i++ {fmt.Scanf("%d", &arr[i])}mergeSort(arr, 0, n-1)for i := 0; i < n; i++ {fmt.Printf("%d ", arr[i])}
}
模板
void merge_sort(int q[], int l, int r)
{if (l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
相关文章:
AcWing 787. 归并排序——算法基础课题解
AcWing 787. 归并排序 文章目录 题目描述CGo模板 题目描述 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n。 第二行包含 n 个整数(所有…...
力扣1379---找出克隆二叉树的相同节点(Java、DFS、简单题)
目录 题目描述: 思路描述: 代码: (1): (2): 题目描述: 给你两棵二叉树,原始树 original 和克隆树 cloned,以及一个位于原始树 ori…...
FLink学习(三)-DataStream
一、DataStream 1,支持序列化的类型有 基本类型,即 String、Long、Integer、Boolean、Array复合类型:Tuples、POJOs 和 Scala case classes Tuples Flink 自带有 Tuple0 到 Tuple25 类型 Tuple2<String, Integer> person Tuple2.…...
Failed to resolve import “Home/components/HomeNew.vue“. Does the file exist?
错误信息 [plugin:vite:import-analysis] Failed to resolve import "/apis/home.js" from "src/views/Home/components/HomeNew.vue". Does the file exist? 错误原因 路径错误 解决方法...
《价值》-张磊-高瓴资本-3-建立人脉和信任;顺应趋势,把握机遇;
第三章 价值投资初试炼 2005.6.1 创办高瓴资本 许多人问我为什么一直在创业,其实我倒没想到自己非要创业成功不可,只是觉得一定要做点事,做点有意义的事。归根到底,可能是“爱折腾,不满足现状,爱挑战自己”…...
游戏引擎中的物理应用
一、 角色控制器 Character Controller和普通的动态对象(Dynamic Actor )是不同的,主要的三个特点是: 它拥有可控制的刚体间的交互假设它是有无穷的摩擦力(可以站停在位置上),没有弹性加速和刹车几乎立即…...
复现k8s黄金票据学习
1.什么是黄金票据 在 Kubernetes 中,"黄金票据"并不是一个常见的术语。可能你想了解的是服务账户(Service Account)。服务账户是 Kubernetes 中用于身份验证和授权的一种机制。它们允许 Pods 或其他工作负载在 Kubernetes 集群中与…...
08-JavaScript BOM定时器及JS动画
1. 设置定时器 1.1设置超时定时器 超时调用需要使用window对象的setTimeout()方法,该方法接受两个参数:调用函数或计算表达式和以毫秒为单位的时间(即在执行代码前需要等待多少毫秒)。 //setTimeout(callback, after) //callba…...
边缘计算盒子与云计算:谁更适合您的业务需求?
边缘计算盒子和云计算,这两个概念听起来可能有点复杂,但其实它们就是两种不同的数据处理方式。那谁更适合您的业务需求呢?咱们来详细说说。 边缘计算盒子,就像是个小型的数据处理中心,放在离你业务现场比较近的地方。它…...
浅聊什么是Redis?
需求:MySQL面临大量的查询,即读写操作,因此类比CPU,给数据加缓存,Redis诞生。应用程序从MySQL查询的数据,在Redis设置缓存(记录在内存中,无需IO操作),后再需要…...
java算法day43 | ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零
1049. 最后一块石头的重量 II 核心思想: 尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头,一堆石头的…...
练气第六天
问:ANR怎么分析? ANR问题,这其实是一个非常综合性的问题,因为anr会涉及CPU负载,内存空间大小,线程锁,GC回收,这里面每个点,都是非常考验我们基本功的。 分析ANR问题,需…...
认识 Redis 与 分布式
Redis 官网页面 Redis官网链接 Redis 的简介 Redis 是一个在内存中存储数据的中间件 一方面用于作为数据库,另一方面用于作为数据缓存,适用于分布式系统中 Redis 基于网络,进行进程间通信,把自己内存中的变量给别的进程…...
Linux初学(十二)AWK进阶
一、AWK 1.1 简介 AWK是Linux中重要的文本处理工具Linux三剑客只一处理的对象可以是一个具体的文件,也可以是一个命令的执行结果AWK按行读取文件,将每一行视为一条记录 案例一:获取系统中每个用户的uid 方法一:cat /etc/passwd |…...
文字识别 Optical Character Recognition,OCR CTC STN
文字识别 Optical Character Recognition,OCR 自然场景文本检测识别技术综述 将图片上的文字内容,智能识别成为可编辑的文本。 场景文字识别(Scene Text Recognition,STR) OCR(Optical Character Recognition, 光学字符识别)传统上指对输入扫描文档图像进行分析处理,识…...
四、MySQL读写分离之MyCAT
一、读写分离概述 1、什么是读写分离: 读写分离:就是将读写操作分发到不同的服务器,读操作分发到对应的服务器 (slave),写操作分发到对应的服务器(master) ① M-S (主从) 架构下&…...
通讯录项目实现
引言:通过顺序表的逻辑实现通讯录。这里就不讲关于顺序表的函数了。如果有不明白的可以看我写的顺序表的博客。 目录 顺序表与通讯录的比较 各源文件文件大榄 Contact.c中通讯录相关函数的定义 初始化和销毁通讯录 添加联系人: 删除联系人…...
xss相关知识点与绕过思路总结
前言 对xss的绕过进行了系统的学习与实践后,重新审视一下xss,对他的绕过进行一个总结。 (当然我也是个小白,这些也是我当时瞎鸡儿乱搞绕过了几个xss自己做的小总结) 可能有点丑陋,献丑了。 好博客推荐 …...
深入解析语言模型:原理、实战与评估
引言 随着人工智能的飞速发展,语言模型作为自然语言处理(NLP)的核心技术之一,日益受到业界的广泛关注。本文旨在深入探讨语言模型的原理、实战应用以及评估方法,帮助读者更好地理解和应用这一技术。 一、语言模型原理…...
Elasticsearch 的索引优化常规项
优化常规项 https://blog.csdn.net/bairo007/article/details/132019575 1、按实际情况适当调整主分片的数量 如果主分片数量太少,会导致每个分片中的数据量过大,而且无法利用集群中所有节点的计算资源。如果主分片数量太多,会导致索引过度…...
【JavaParser笔记01】JavaParser解析Java源代码中的类信息(javadoc注释、类名称)
这篇文章,主要介绍如何使用JavaParser解析Java源代码中的类信息(javadoc注释、类名称)。 目录 一、JavaParser依赖库 1.1、引入依赖 1.2、获取类注释信息...
Stable Diffusion扩散模型【详解】小白也能看懂!!
文章目录 1、Diffusion的整体过程2、加噪过程2.1 加噪的具体细节2.2 加噪过程的公式推导 3、去噪过程3.1 图像概率分布 4、损失函数5、 伪代码过程 此文涉及公式推导,需要参考这篇文章: Stable Diffusion扩散模型推导公式的基础知识 1、Diffusion的整体…...
关于rabbitmq的prefetch机制
消息预取机制(Prefetch Mechanism)是RabbitMQ中用于控制消息传递给消费者的一种机制。它定义了在一个信道上,消费者允许的最大未确认的消息数量。一旦未确认的消息数量达到了设置的预取值,RabbitMQ就会停止向该消费者发送更多消息…...
机器学习介绍
机器学习是人工智能(AI)的一个分支,它使计算机系统能够从数据中学习并改进它们的性能。机器学习的核心在于开发算法,这些算法可以从大量数据中识别模式和特征,并用这些信息来做出预测或决策,而无需进行明确…...
OpenCV4.9开发之Window开发环境搭建
1.打开OpenCV所在github地址 2.点击opencv仓库,进入仓库详情,点击右下方的OpenCV 4.9.0进入下载页面 3.点击opencv-4.9.0-windows.exe下载 开始下载中... 下载完成 下载完成后,双击运行解压,默认解压路径,修改为c:/...
DDD 中的实体和值对象有什么区别?
在DDD中,实体 Entity 和值对象 Value Object 是两个基本的概念,它们之间有一些重要的区别。 唯一性:实体是唯一的,每个实体都有一个唯一的标识符,即使它的属性在一段时间内发生了变化,它仍然是这个实体。与…...
算法-最值问题
#include<iostream> using namespace std; int main() {int a[7];//上午上课时间int b[7];//下午上课时间int c[7];//一天总上课时间for (int i 0; i < 7; i) {cin >> a[i] >> b[i];c[i] a[i] b[i];}int max c[0];//max记录最长时间int index -1;//索…...
Go 性能压测工具之wrk介绍与使用
在项目正式上线之前,我们通常需要通过压测来评估当前系统能够支撑的请求量、排查可能存在的隐藏bug;压力测试(压测)是确保系统在高负载情况下仍能稳定运行的重要步骤。通过模拟高并发场景,可以评估系统的性能瓶颈、可靠…...
数学思想论(有目录)
数学思想是数学发展过程中的重要指导原则,它涉及对数学概念、方法和理论的理解和认识,以及如何利用这些工具来解决实际问题。数学思想的形成和演进是随着数学的发展而逐渐深化的,它体现了人类对数学本质和应用的不断探索和思考。 一些主要的数学思想包括: 函数与方程思想…...
C++的并发世界(五)——线程状态切换
0.线程状态 初始化:该线程正在被创建; 就绪:该线程在列表中就绪,等待CPU调度; 运行:该线程正在运行; 阻塞:该线程被阻塞挂机,Blocked状态包括:pendÿ…...
营销类网站有哪些/网站推广的途径有哪些
软件生命周期(SDLC)的六个阶段 1、问题的定义及规划此阶段是软件开发方与需求方共同讨论,主要确定软件的开发目标及其可行性。2、需求分析在确定软件开发可行的情况下,对软件需要实现的各个功能进行详细分析。需求分析阶段是一个很重要的阶段,…...
吴兴网站建设/市场调研报告的基本框架
基于单片机的智能豆浆机控制系统设计(附实物图,电路原理图,程序)(任务书,开题报告,中期检查表,毕业论文11800字)摘要由于市面上的豆浆机不具有长时间保温的功能,打浆完成后残渣很多,而且打浆用时较长。因此,本次设计制作了基于51单片机的全自…...
公司备案证查询网站查询网站/自动收录网
2019独角兽企业重金招聘Python工程师标准>>> 本文首发于IBM Developeworks:http://www.ibm.com/developerworks/cn/web/1202_zhouxiang_dojocometd/,感谢JayZ的投稿。 简介: 服务器推送技术已经出来一段时间了,业界上也…...
个人网站做百度竞价/网络营销的方法包括哪些
文章目录场景复现原因分析解决方法ListMap场景复现 对于list,map都有可能出现,这里主要分析list! Testpublic void testList() {List<String> list new ArrayList();list.add("1");list.add("2");list.add("…...
网站开发准备/潍坊网站定制模板建站
IOC(Inversion of Control)即控制反转,它是一种思想。 在这过程中,对象创建后通过在对象实例上设置属性来定义他们间的依赖关系,然后IOC容器在创建bean的时候注入这些依赖。在传统应用程序中, 可以在对象中通过new创建依赖的对象&…...
2019年做网站还有机会吗/制造业中小微企业
Determine file-access permission.int _access( const char *path, int mode );声明于 io.h #include <io.h> C _access和_waccess的使用方法 概述 头文件:<io.h> 判断文件的访问权限 原型 int _access( const char *path, int mode ); i…...