归并排序例题——逆序对的数量

做道简单一点的题巩固一下

归并排序实现步骤
将整个区间 [l, r] 划分为 [l, mid] 和 [mid+1, r]。
递归排序 [l, mid] 和 [mid+1, r]。
将左右两个有序序列合并为一个有序序列。

题目描述

给定一个长度为 n 的整数数列,请计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。

输入格式
输入共两行。
第一行包含整数 n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。

输出格式
输出一个整数,表示逆序对的个数。

数据范围
1≤n≤100000
数列中的元素的取值范围 [1,1e9]。

输入样例
6
2 3 4 5 6 1

输出样例
5

具体实现
实现思路:

可以将所有的逆序对整体分为3大类

两个数同时出现在左半边(红色);
两个数同时出现在右半边(绿色);
一个数在左半边,一个数在右半边(黄色)。

因此,我们在归并排序的同时便要记录逆序对的个数。

红色情况时逆序对数量:merge_sort(l,mid);
绿色情况时逆序对数量:merge_sort(mid+1,r);
黄色情况时逆序对数量:先将左右两边分别变为有序序列,然后双指针进行比较,先选取右边序列当中第一个元素,判断左边序列当中有几个元素大于他,便有几个逆序对(即分别选取右边序列中的每一个元素,然后分别遍历左边序列当中的每个元素,进行比较判断,最后累加起来)。

代码注解:

n的最大值为100000,我们计算最坏情况,即数列时降序排列,就一共有 n(n-1)/2 个逆序对,即 5*1e9 个逆序对,可能会有大于 int 值的情况,因此使用 long long 进行存储。
因为左右两个均为有序数列,所有当左边序列第 i 个元素大于右边序列第 j 个元素的时候,左边序列 [i,mid] 都严格大于右边序列第 j 个元素,即 mid-i+1 个逆序对,就是我们归并排序归并的过程,所以每当我们输出一个 q[i]>q[j] 的情况,便在逆序对个数上加一个 mid-i+1 。
要注意 merge_sort 的返回值类型变为 long long ,否则会造成数据过多时无法AC。

实现代码
 

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N=100010;
int n;
int q[N],temp[N];
ll merge_sort(int q[],int l,int r)
{if(l>=r){return 0;}else{int mid=l+r>>1;ll res=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]){temp[k]=q[i];k++;i++;}else{temp[k]=q[j];k++;j++;res+=mid-i+1;}}while(i<=mid){temp[k]=q[i];k++;i++;}while(j<=r){temp[k]=q[j];k++;j++;}for(i=l,j=0;i<=r;i++,j++){q[i]=temp[j];}return res;}
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>q[i];}cout<< merge_sort(q,0,n-1)<<endl;system("pause");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/236450.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java面试题(java高级面试题)

线程池的核心线程数设置为多大比较合理&#xff1f; Worker线程在执行的过程中&#xff0c;有一部计算时间需要占用CPU&#xff0c;另一部分等待时间不需要占用CPU&#xff0c;通过量化分析&#xff0c;例如打日志进行统计&#xff0c;可以统计出整个Worker线程执行过程中这两…

微信小程序开发学习笔记《8》tabBar

微信小程序开发学习笔记《8》tabBar 博主正在学习微信小程序开发&#xff0c;希望记录自己学习过程同时与广大网友共同学习讨论。tabBar官方文档 tabBar这一节还是相当重要的。 一、什么是tabBar tabBar是移动端应用常见的页面效果&#xff0c;用于实现多页面的快速切换。小…

GC2003七通道NPN 达林顿管,专为符合标准 TTL 而制造

GC2003 内部集成了 7 个 NPN 达林顿晶体管&#xff0c;连接的阵列&#xff0c;非常适合逻辑接口电平数字电路&#xff08;例 如 TTL&#xff0c;CMOS 或PMOS 上/NMOS&#xff09;和较高的电流/电压&#xff0c;如电灯电磁阀&#xff0c;继电器&#xff0c;打印机或其他类似的负…

NAND Separate Command Address (SCA) 接口数据传输解读

在采用Separate Command Address (SCA) 接口的存储产品中&#xff0c;DQ input burst和DQ output burst又是什么样的策略呢&#xff1f; DQ Input Burst: 在读取操作期间&#xff0c;数据以一种快速并行的方式通过DQ总线传送到控制器。在SCA接口下&#xff0c;虽然命令和地址信…

设计一个简易版的数据库路由

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring原理、JUC原理、Kafka原理、分布式技术原理、数据库技术&#x1f525;如果感觉博主的文章还不错的…

黑马苍穹外卖学习Day5

文章目录 Redis学习Redis简介准备工作Redis常用数据类型介绍各数据类型的特点Redis常用命令字符串操作命令哈希操作命令列表操作命令集合操作命令有序集合操作命令通用操作命令 在Java中操作Redis导入Spring Data Redis坐标配置Redis数据源编写配置类&#xff0c;创建RedisTemp…

从事铁路工作保护足部,穿什么劳保鞋更安全

铁路运输在我国交通运输业中起着骨干作用&#xff0c;为国民经济的可持续发展和人口流动做出了巨大贡献。安全是铁路运输不可忽视的问题&#xff0c;在作业场地随处能见到“安全就是生命&#xff0c;责任重于泰山”的安全标语&#xff0c;由此可见安全问题是放在首位的。 铁路施…

开源游戏引擎:创造无限可能 | 开源专题 No.56

godotengine/godot Stars: 62.6k License: MIT Godot Engine 是一个功能强大的跨平台游戏引擎&#xff0c;可用于创建 2D 和 3D 游戏。它提供了一套全面的常见工具&#xff0c;让用户可以专注于制作游戏而不必重复造轮子。该引擎支持将游戏一键导出到多个平台上&#xff0c;包…

代码随想录Day.31 | 455. 分发饼干、376. 摆动序列、53. 最大子序和

455. 分发饼干 1. LeetCode链接 455. 分发饼干 - 力扣&#xff08;LeetCode&#xff09; 2. 题目描述 3. 解法 贪心法&#xff0c;首先想到的是&#xff0c;局部最优&#xff1a;让每个孩子尽可能拿能拿到的最小饼干尺寸。为了方便查找&#xff0c;这就要求至少饼干尺寸是从…

shell中的正则表达式、编程-grep、编程-SED、以及编程-AWK

正则表达式RE 用来处理文本 正则表达式(Regular Expression, RE)是一种字符模式, 用于在查找过程中匹配指定的字符. 在大多数程序里, 正则表达式都被置于两个正斜杠之间; 例如/l[oO]ve/就是由正斜杠界定的正则表达式, 它将匹配被查找的行中任何位置出现的相同模式. 在正则表达…

react antd EditableProTable - 可编辑表格

与编辑表格外的内容联动 value 同 dataSource&#xff0c;传入一个数组,是 table 渲染的元数据 T[] undefined onChange dataSource 修改时触发&#xff0c;删除和修改都会触发,如果设置了 value&#xff0c;Table 会成为一个受控组件。 (value:T[])>void undefined recordC…

[易语言]使用易语言部署工业级人脸检测模型

【框架地址】 https://github.com/ShiqiYu/libfacedetection 【算法介绍】 Libfacedetection是一个开源的计算机视觉库&#xff0c;主要用于实时的人脸检测。它利用深度学习技术&#xff0c;特别是卷积神经网络&#xff08;CNN&#xff09;&#xff0c;实现了高精度的脸部定位…

GlusterFS

一. 概念 1. 介绍 gluster是一个横向扩展的分布式文件系统&#xff0c;可将来自多个服务器的磁盘存储资源整合到一个全局名称空间中&#xff0c;可以根据存储消耗需求快速调配额外的存储。它将自动故障转移作为主要功能. 分布式存储系统.集群式NAS存储.无集中式元数据服务,采…

ChatGLM2-6B 大语言模型本地搭建

ChatGLM模型介绍&#xff1a; ChatGLM2-6B 是清华 NLP 团队于不久前发布的中英双语对话模型&#xff0c;它具备了强大的问答和对话功能。拥有最大32K上下文&#xff0c;并且在授权后可免费商用&#xff01; ChatGLM2-6B的6B代表了训练参数量为60亿&#xff0c;同时运用了模型…

Python笔记08-面向对象

文章目录 类和对象构造方法内置方法封装继承类型注解多态 类只是一种程序内的“设计图纸”&#xff0c;需要基于图纸生产实体&#xff08;对象&#xff09;&#xff0c;才能正常工作 这种套路&#xff0c;称之为&#xff1a;面向对象编程 类和对象 定义类的语法如下&#xff…

K8S集群重新初始化--详细过程

K8S集群重新初始化 0、当前环境1、master节点1.1、在master节点执行下面reset命令&#xff1a;1.2、手动清除配置信息&#xff0c;这一步很关键&#xff1a;1.3、重新引导集群1.4、创建配置目录&#xff0c;并复制权限配置文件到用户目录下&#xff1a;1.5 查看集群状态1.6 安装…

提升测试效率,轻松并行运行测试——探秘Pytest插件pytest-xdist

在软件开发中&#xff0c;测试是确保代码质量的重要一环。然而&#xff0c;随着项目规模的增大&#xff0c;测试用例的数量也随之增多&#xff0c;测试的执行时间可能成为一个瓶颈。为了解决这个问题&#xff0c;Pytest提供了丰富的插件生态系统&#xff0c;其中 pytest-xdist …

从vue小白到高手,从一个内容管理网站开始实战开发第八天,登录功能后台功能设计--业务逻辑层基础接口和基础服务实现

上一篇我们介绍了项目后续要使用到的工具类,关于工具类的创建可以查看 从vue小白到高手,从一个内容管理网站开始实战开发第七天,登录功能后台功能设计--通用分页、枚举以及相关工具类-CSDN博客文章浏览阅读2次。本次内容主要介绍了项目后续用到的部分工具类,这些工具类,在…

基于博弈树的开源五子棋AI教程[3 极大极小搜索]

基于博弈树的开源五子棋AI教程[3 极大极小搜索] 引子极大极小搜索原理alpha-beta剪枝负极大搜索尾记 引子 极大极小搜索是博弈树搜索中最常用的算法&#xff0c;广泛应用于各类零和游戏中&#xff0c;例如象棋&#xff0c;围棋等棋类游戏。算法思想也是合乎人类的思考逻辑的&a…

物理机搭建hive

一、修改Hadoop配置 修改core-site.xml 配置yarn-site.xml 分发文件&#xff0c;然后重启集群 二、 Hive解压安装 上传文件 添加hive环境便量&#xff0c;source生效 启动高可用集群&#xff0c;启动hive 三、配置mysql元数据库 检查当前系统是否安装过Mysql&#xf…