当前位置: 首页 > news >正文

用归并排序算法merge_sort( )求解 逆序对的数量 降低时间复杂度为 nlogn

题目简述
给定一个序列有n个数,求n个数中逆序对的个数,逆序对的定义:i < j && a[i] > a[j]。

输入格式

第一行包含一个整数n。

第二行包含 n 个整数(所有整数均在1~1e9范围内),表示整数数列。

输出格式

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

输入样例:

6
2 3 4 5 6 1
输出样例:

5

归并排序应用
归并排序是将一个序列分成两个有序的序列,归并两个有序序列,归并后则该序列有序,是基于分治的思想。

根据逆序对的定义,我们也可以使用分治的算法来求解逆序对的数量。如图:

我们将序列分成两部分,我们发现逆序对的数量是三种逆序对数量的和:

左边序列的逆序对
右边序列的逆序对
横跨中间的逆序对

利用归并排序,我们可以分别求解左边序列的逆序对的数量和右边序列的逆序对的数量。如何求解横跨中间逆序对的数量呢?
归并排序中归并的过程:

意味着在归并两个序列的过程中,我们就可以计算出横跨中间的逆序对的数量。
时间复杂度O(nlogn),空间复杂度O(N)

//下面的代码是在归并排序的基础上做了改进,不同在于有返回值,递归终止条件,归并第二个序列。
int merge_sort(int a[], int l ,int r){//序列只有一个数if (l == r) return 0;//递归左边和右边int mid = l + r >> 1;int res = merge_sort(a, l , mid) + merge_sort(a, mid + 1, r);//归并的过程int i = l , j = mid + 1, k = 0;while (i <= mid && j <= r){if (a[i] <= a[j]) t[k++] = a[i++];else{t[k++] = a[j++];res += mid - i + 1;}}while (i <= mid) t[k++] = a[i++];while (j <= r) t[k++] = a[j++];//还原数组for (int i = 0 , j = l ; j <= r ; i ++ , j ++) a[j] = t[i];return res;
}


 

相关文章:

用归并排序算法merge_sort( )求解 逆序对的数量 降低时间复杂度为 nlogn

题目简述 给定一个序列有n个数&#xff0c;求n个数中逆序对的个数&#xff0c;逆序对的定义&#xff1a;i < j && a[i] > a[j]。 输入格式 第一行包含一个整数n。 第二行包含 n 个整数&#xff08;所有整数均在1~1e9范围内&#xff09;&#xff0c;表示整数数…...

大功率电源芯片WD5030L

电源管理芯片作为现代电子设备中最关键的元件之一&#xff0c;直接影响着设备的性能和效率。而大功率电源芯片作为电源管理芯片中的一种&#xff0c;其性能和应用领域更加广泛。本文将介绍一款具有宽VIN输入范围、高效率和多种优良性能的大功率电源芯片WD5030L&#xff0c;并探…...

Spring Boot使用EhCache完成一个缓存集群

在上一篇在SpringBoot中使用EhCache缓存&#xff0c;我们完成了在Spring Boot中完成了对EhCaChe的使用&#xff0c;这篇&#xff0c;我们将对EhCache的进一步了解&#xff0c;也就是搭建一个EhCache的缓存集群。 集群 在搭建一个EhCache的时候&#xff0c;我们需要先了解&…...

yolov5模型代码怎么修改

yaml配置文件 深度乘积因子 宽度乘积因子 所有版本只有这两个参数的不同&#xff0c;s m l x逐渐加宽加深 各种类型层参数对照 backbone里的各层&#xff0c;在这里解析&#xff0c;只需要改.yaml里的各层参数就能控制网络结构 修改网络结构 第一步&#xff1a;把新加的模块…...

VIM去掉utf-8 bom头

Windows系统的txt文件在使用utf-8编码保存时会默认在文件开头插入三个不可见的字符&#xff08;0xEF 0xBB 0xBF&#xff09;称为BOM头 BOM头文件 0.加上BOM标记&#xff1a; :set bomb 1.查询当前UTF-8编码的文件是否有BOM标记&#xff1a; :set bomb? :set bomb? 2.BOM头:文…...

Go 使用Viper处理Go应用程序的配置

在开发Go应用程序时&#xff0c;处理配置是一个常见的需求。配置可能来自于配置文件、环境变量、命令行参数等等。Viper是一个强大的库&#xff0c;可以帮助我们处理这些配置。 什么是Viper&#xff1f; Viper是一个应用程序配置解决方案&#xff0c;用于Go应用程序。它支持JS…...

hadoop安装网址

Hadoop是什么 1&#xff09;Hadoop是一个有Apache基金会所开发的分布式系统基础架构。 2&#xff09;主要解决海量数据的存储和海量数据的分析计算问题。 3&#xff09;广义上来说&#xff0c;Hadoop通常是指一个更广泛的概念---Hadoop生态圈。 Hadoop发行版本 Hadoop发行的…...

JavaMail邮件发送服务

记录一次使用基于SpringBoot来设置发送邮件的服务 导入依赖 <!--邮件发送--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId><version>${springboot.version}</ve…...

【918.环形子数组的最大和】

目录 一、题目描述二、算法原理三、代码实现 一、题目描述 二、算法原理 三、代码实现 class Solution { public:int maxSubarraySumCircular(vector<int>& nums) {int sum0;for(auto x:nums) sumx;vector<int> f(nums.size());vector<int> g(nums.size…...

Unity Quaternion接口API的常用方法解析_unity基础开发教程

Quaternion接口的常用方法 Quaternion.Euler()Quaternion.Lerp()Quaternion.Inverse()Quaternion.RotateTowards() Quaternion在Unity中是一种非常重要的数据类型&#xff0c;用于表示3D空间中的旋转。Quaternion可以表示任何旋转&#xff0c;无论是在哪个轴上旋转多少度&#…...

Rust开发——使用rust实现Redis中hset

一、Redis中hset HSET 是 Redis 中用于在哈希数据结构中设置指定字段的值的命令。哈希是一种类似于字典或映射的数据结构&#xff0c;它存储了键值对的集合&#xff0c;其中每个键都包含多个字段和与这些字段相关联的值。 哈希表在 Redis 中以键值对形式存储&#xff0c;并通…...

海康Visionmaster-环境配置:VB.Net 二次开发环境配 置方法

Visual Basic 进行 VM 二次开发的环境配置分为三步。 第一步&#xff0c;使用 VS 新建一个框架为.NET Framework 4.6.1&#xff0c;平台去勾选首选 32 为的工程&#xff0c;重新生成解决方案&#xff0c;保证工程 Debug 下存在 exe 文件&#xff0c;最后关闭新建工程&#xff1…...

51单片机应用从零开始(四)

51单片机应用从零开始&#xff08;一&#xff09;-CSDN博客 51单片机应用从零开始&#xff08;二&#xff09;-CSDN博客 51单片机应用从零开始&#xff08;三&#xff09;-CSDN博客 详解 KEIL C51 软件的使用建立工程-CSDN博客 详解 KEIL C51 软件的使用设置工程编绎与连接程序…...

Django下的Race Condition漏洞

目录 环境搭建 无锁无事务的竞争攻击复现 无锁有事务的竞争攻击复现 悲观锁进行防御 乐观锁进行防御 环境搭建 首先我们安装源码包&#xff1a;GitHub - phith0n/race-condition-playground: Playground for Race Condition attack 然后将源码包上传到Ubuntu 为了方便使…...

【数据结构】希尔排序(最小增量排序)

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前正在学习c和算法 ✈️专栏&#xff1a;数据结构 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助…...

Android Native崩溃信息分析和 工具(addr2line和ndkstack)使用

这里以一个实际的crash案例未demo进行分析和讲解。针对native的崩溃信息。一般来讲&#xff0c;较快的方式是直接检索到backtrace&#xff0c;然后通过分析和使用工具addr2line和 ndk-stack等定位到出问题的地方。这里截取了一段 崩溃日志&#xff0c;具体如下&#xff1a; 01…...

2023年05月 Python(六级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 明明每天坚持背英语单词,他建立了英语单词错题本文件“mistakes.txt”,将每天记错的单词增加到该文件中,下列打开文件的语句最合适的是?( ) A: f = open(“mistakes.txt”) B: …...

SQLite3 数据库学习(文章链接汇总)

参考引用 SQLite 权威指南&#xff08;第二版&#xff09;SQLite3 入门 SQLite3 数据库学习&#xff08;一&#xff09;&#xff1a;数据库和 SQLite 基础 SQLite3 数据库学习&#xff08;二&#xff09;&#xff1a;SQLite 中的 SQL 语句详解 SQLite3 数据库学习&#xff08;三…...

【VSCode】Visual Studio Code 下载与安装教程

前言 Visual Studio Code&#xff08;简称 VS Code&#xff09;是一个轻量级的代码编辑器&#xff0c;适用于多种编程语言和开发环境。本文将介绍如何下载和安装 Visual Studio Code。 下载安装包 首先&#xff0c;我们需要从官方网站下载 Visual Studio Code 的安装包。请访…...

分布式教程从0到1【1】分布式基础

1 分布式基础概念 1.1 微服务 微服务架构风格&#xff0c;就像是把一个单独的应用程序开发为一套小服务&#xff0c;每个小服务运行在自己的进程中&#xff0c;并使用轻量级机制通信&#xff0c;通常是 HTTP API。这些服务围绕业务能力来构建&#xff0c;并通过完全自动化部署…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...