当前位置: 首页 > 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;并通过完全自动化部署…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

Yolo11改进策略:Block改进|FCM,特征互补映射模块|AAAI 2025|即插即用

1 论文信息 FBRT-YOLO&#xff08;Faster and Better for Real-Time Aerial Image Detection&#xff09;是由北京理工大学团队提出的专用于航拍图像实时目标检测的创新框架&#xff0c;发表于AAAI 2025。论文针对航拍场景中小目标检测的核心难题展开研究&#xff0c;重点解决…...