offer题目51:数组中的逆序对
题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如,在数组{7,5,6,4}中,一共存在5个逆序对,分别是(7,6)、(7,5)、(7,4)、(6,4)、(5,4)。
分析:可以用类似归并排序的思想,将数组二分,直到数组中只有一个元素时,此时数组逆序数组个数为0,然后开始合并数组,分别统计两个合并数组中逆序对的个数,这样自底向上地完成数组的排序及逆序对的统计,实际上是和归并排序是相同的方法。
具体地对于计算统计两个子数组的逆序对的个数,我们用两个指针分别指向两个子数组的末尾,并每次比较两个指针指向的数字,如果第一个子数组中的数字大于第二个子数组中的数字,则构成逆序对,并且逆序对的数目等于第二个子数组中剩余数字的个数。如果第一个数组中的数字小于或等于第二个数组中的数字,则不构成逆序对。每次比较,我们都把较大的数字从后往前复制到一个辅助数组,确保辅助数组中的数字是递增排列。
int InversePairs(int* data,int length){if(data == nullptr || length < 0){return 0;}int* copy = new int[length];for(int i = 0;i < length;++i){ //用一个辅助数组存放排序后的数组元素copy[i] = data[i]; //****归并排序需要将辅助数组元素merge回原数组完成排序*****//}int count = InversePairsCore(data,copy,0,length - 1);//如果要保存排序后的数组可将data和copy参数交换位置:即InversePairCore(copy,data,0,length - 1);delete[] copy;return count;
}int InversePairsCore(int* data,int* copy,int start,int end){if(start == end){ //数组中只有一个元素,返回0// copy[start] = data[start]; return 0;}int length = (end - start) / 2;int left = InversePairsCore(copy,data,start,start + length); //copy数组中存放已排序的子数组,接下来会对copy数组作合并和排序操作,//操作的结果放在data数组中,作为下一次合并排序的copy数组(即两个数组,是互相备份的关系), //***此操作也修改了原输入数组中的元素值***int right = InversePairsCore(copy,data,start + length + 1,end);//i初始化为前半段最后一个元素的一下标int i = start + length;//j初始化为后半段最后一个元素的一下标int j = end;int indexCopy = end; //辅助数组的下标元素从数组结尾开始int count = 0;while(i >= start && j >= start + length + 1){if(data[i] > data[j]){copy[indexCopy--] = data[i--];count += j - start - length;}else{copy[indexCopy--] = data[j--];}}for(;i >= start;--i){copy[indexCopy--] = data[i];}for(;j >= start + length + 1;--j){copy[indexCopy--] = data[j];}return left + right + count;
}
相关文章:
offer题目51:数组中的逆序对
题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如,在数组{7,5,6,4}中,一共存在5个逆序对,分别是(7…...
45、PHP 实现滑动窗口的最大值
题目: PHP 实现滑动窗口的最大值 描述: 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。 例如: 如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3, 那么一共存在6个滑动窗口, 他们的最大值…...
【计算机视觉】siamfc论文复现实现目标追踪
什么是目标跟踪 使用视频序列第一帧的图像(包括bounding box的位置),来找出目标出现在后序帧位置的一种方法。 什么是孪生网络结构 孪生网络结构其思想是将一个训练样本(已知类别)和一个测试样本(未知类别)输入到两个CNN(这两个CNN往往是权值共享的)中࿰…...
数学建模学习(111):改进遗传算法(引入模拟退火、轮盘赌和网格搜索)求解JSP问题
文章目录 一、车间调度问题1.1目前处理方法1.2简单案例 二、基于改进遗传算法求解车间调度2.1车间调度背景介绍2.2遗传算法介绍2.2.1基本流程2.2.2遗传算法的基本操作和公式2.2.3遗传算法的优势2.2.4遗传算法的不足 2.3讲解本文思路及代码2.4算法执行结果: 三、本文…...
Golang | Leetcode Golang题解之第241题为运算表达式设计优先级
题目: 题解: const addition, subtraction, multiplication -1, -2, -3func diffWaysToCompute(expression string) []int {ops : []int{}for i, n : 0, len(expression); i < n; {if unicode.IsDigit(rune(expression[i])) {x : 0for ; i < n &…...
Unity客户端接入原生Google支付
Unity客户端接入原生Google支付 1. Google后台配置2. 开始接入Java部分C#部分Lua部分 3. 导出工程打包测试参考踩坑注意 1. Google后台配置 找到内部测试(这个测试轨道过审最快),打包上传,这个包不需要接入支付,如果已…...
Spring Cloud之五大组件
Spring Cloud 是一系列框架的有序集合,为开发者提供了快速构建分布式系统的工具。这些组件可以帮助开发者做服务发现,配置管理,负载均衡,断路器,智能路由,微代理,控制总线等。以下是 Spring Cl…...
在 CentOS 7 上安装 Docker 并安装和部署 .NET Core 3.1
1. 安装 Docker 步骤 1.1:更新包索引并安装依赖包 先安装yum的扩展,yum-utils提供了一些额外的工具,这些工具可以执行比基本yum命令更复杂的任务 sudo yum install -y yum-utils sudo yum update -y #更新系统上已安装的所有软件包到最新…...
redis的学习(一):下载安装启动连接
简介 redis的下载,安装,启动,连接使用 nosql nosql,即非关系型数据库,和传统的关系型数据库的对比: sqlnosql数据结构结构化非结构化数据关联关联的非关联的查询方式sql查询非sql查询事务特性acidbase存…...
前端设计模式面试题汇总
面试题 1. 简述对网站重构的理解? 参考回答: 网站重构:在不改变外部行为的前提下,简化结构、添加可读性,而在网站前端保持一致的行为。也就是说是在不改变UI的情况下,对网站进行优化, 在扩展的…...
linux(CentOS、Ubuntu)安装python3.12.2环境
1.下载官网Python安装包 wget https://www.python.org/ftp/python/3.12.2/Python-3.12.2.tar.xz 1.1解压 tar -xf Python-3.12.2.tar.xz 解压完后切换到Python-3.12.2文件夹(这里根据自己解压的文件夹路径) cd /usr/packages/Python-3.12.2/ 1.2升级软件包管理器 CentOS系…...
CSS 中border-radius 属性
border-radius 属性在 CSS 中用于创建圆角边框。它可以接受一到四个值,这些值可以是长度值(如像素 px、em 等)或百分比(%)。当提供四个值时,它们分别对应于边框的左上角、右上角、右下角和左下角的圆角半径…...
【大数据专题】数据仓库
1. 简述数据仓库架构 ? 数据仓库的核心功能从源系统抽取数据,通过清洗、转换、标准化,将数据加载到BI平台,进而满足业 务用户的数据分析和决策支持。 数据仓库架构包含三个部分:数据架构、应用程序架构、底层设施 1&…...
go关于string与[]byte再学深一点
目标:充分理解string与[]bytes零拷贝转换的实现 先回顾下string与[]byte的基本知识 1. string与[]byte的数据结构 reflect包中关于字符串的数据结构 // StringHeader is the runtime representation of a string.type StringHeader struct {Data uintptrLen int} …...
Qt 实战(7)元对象系统 | 7.4、属性系统:深度解析与应用
文章目录 一、属性系统:深度解析与应用1、定义属性2、属性系统的作用3、属性系统工作原理(1)Q_PROPERTY宏(2)moc 的作用(3)属性在元对象中的注册 4、获取与设置属性4.1、QObject::property()与Q…...
Docker核心技术:容器技术要解决哪些问题
云原生学习路线导航页(持续更新中) 本文是 Docker核心技术 系列文章:容器技术要解决哪些问题,其他文章快捷链接如下: 应用架构演进容器技术要解决哪些问题(本文)Docker的基本使用Docker是如何实…...
sklearn中的增量学习:特征提取的艺术
sklearn中的增量学习:特征提取的艺术 在机器学习领域,特征提取是构建有效模型的关键步骤。然而,并非所有数据集都适合一次性加载到内存中进行处理,尤其是在处理大规模数据集时。Scikit-learn(sklearn)提供…...
PostgreSQL 中如何处理数据的唯一性约束?
🍅关注博主🎗️ 带你畅游技术世界,不错过每一次成长机会!📚领书:PostgreSQL 入门到精通.pdf 文章目录 PostgreSQL 中如何处理数据的唯一性约束?一、什么是唯一性约束二、为什么要设置唯一性约束…...
VAE论文阅读
在网上看到的VAE解释,发现有两种版本: 按照原来论文中的公式纯数学推导,一般都是了解生成问题的人写的,对小白很不友好。按照实操版本的,非常简单易懂,比如苏神的。但是却忽略了论文中的公式推导ÿ…...
【数据分享】2013-2022年我国省市县三级的逐月SO2数据(excel\shp格式\免费获取)
空气质量数据是在我们日常研究中经常使用的数据!之前我们给大家分享了2000——2022年的省市县三级的逐月PM2.5数据和2013-2022年的省市县三级的逐月CO数据(均可查看之前的文章获悉详情)! 本次我们分享的是我国2013——2022年的省…...
【Jmeter】记录一次Jmeter实战测试
Jmeter实战 1、需求2、实现2.1、新建线程组2.2、导入参数2.3、新建HTTP请求2.4、添加监听器2.5、结果 1、需求 查询某个接口在高并发场景下的响应时间(loadtime),需求需要响应在50ms以内,接下来用Jmeter测试一下 Jmeter安装见文章《Jemeter安装教程&am…...
volatile,最轻量的同步机制
目录 一、volatile 二、如何使用? 三、volatile关键字能代替synchronized关键字吗? 四、总结: 还是老样子,先来看一段代码: 我们先由我们自己的常规思路分析一下代码:子线程中,一直循环&…...
在Linux、Windows和macOS上释放IP地址并重新获取新IP地址的方法
文章目录 LinuxWindowsmacOS 在Linux、Windows和macOS上释放IP地址并重新获取新IP地址的方法各有不同。以下是针对每种操作系统的详细步骤: Linux 使用DHCP客户端:大多数Linux发行版都使用DHCP(动态主机配置协议)来自动获取IP地址…...
Mamba-yolo|结合Mamba注意力机制的视觉检测
一、本文介绍 PDF地址:https://arxiv.org/pdf/2405.16605v1 代码地址:GitHub - LeapLabTHU/MLLA: Official repository of MLLA Demystify Mamba in Vision: A Linear AttentionPerspective一文中引入Baseline Mamba,指明Mamba在处理各种高…...
语音识别标记语言(SSML):自动标识中文多音字
好的,以下是完整的实现代码,包括导入库、分词、获取拼音和生成 SSML 标记的全过程: import thulac from pypinyin import pinyin, Style# 初始化 THULAC thu1 thulac.thulac(seg_onlyTrue)# 测试文本 text "银行行长正在走行。"…...
排序算法与复杂度介绍
1. 排序算法 1.1 排序算法介绍 排序也成排序算法(Sort Algorithm),排序是将一组数据,依照指定的顺序进行排序的过程 1.2 排序的分类 1、内部排序: 指将需要处理的所有数据都加载到**内部存储器(内存&am…...
Kafka介绍及Go操作kafka详解
文章目录 Kafka介绍及Go操作kafka详解项目背景解决方案面临的问题业界方案ELKELK方案的问题日志收集系统架构设计架构设计组件介绍将学到的技能消息队列的通信模型点对点模式 queue发布/订阅 topicKafka介绍Kafka的架构图工作流程选择partition的原则ACK应答机制Topic和数据日志…...
DAY05 CSS
文章目录 1 CSS选择器(Selectors)8. 后代(包含)选择器9. 直接子代选择器10. 兄弟选择器11. 相邻兄弟选择器12. 属性选择器 2 伪元素3 CSS样式优先级1. 相同选择器不同样式2. 相同选择器相同样式3. 继承现象4. 选择器不同权值的计算 4 CSS中的值和单位1. 颜色表示法2. 尺寸表示法…...
HTTPS 的加密过程 详解
HTTP 由于是明文传输,所以安全上存在以下三个风险: 窃听风险,比如通信链路上可以获取通信内容。篡改风险,比如通信内容被篡改。冒充风险,比如冒充网站。 HTTPS 在 HTTP 与 TCP 层之间加入了 SSL/TLS 协议,…...
spring整合mybatis,junit纯注解开发(包括连接druid报错的所有解决方法)
目录 Spring整合mybatis开发步骤 第一步:创建我们的数据表 第二步:编写对应的实体类 第三步:在pom.xml中导入我们所需要的坐标 spring所依赖的坐标 mybatis所依赖的坐标 druid数据源坐标 数据库驱动依赖 第四步:编写SpringC…...
ClusterIP、NodePort、LoadBalancer 和 ExternalName
Service 定义 在 Kubernetes 中,由于Pod 是有生命周期的,如果 Pod 重启它的 IP 可能会发生变化以及升级的时候会重建 Pod,我们需要 Service 服务去动态的关联这些 Pod 的 IP 和端口,从而使我们前端用户访问不受后端变更的干扰。 …...
【Day1415】Bean管理、SpringBoot 原理、总结、Maven 高级
0 SpringBoot 配置优先级 从上到下 虽然 springboot 支持多种格式配置文件,但是在项目开发时,推荐统一使用一种格式的配置 (yml是主流) 1 Bean管理 1.1 从 IOC 容器中获取 Bean 1.2 Bean 作品域 可以通过注解 Scope("proto…...
Git之repo sync -c与repo sync -dc用法区别(四十八)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
vite + vue3 + uniapp 项目从零搭建
vite + vue3 + uniapp 项目从零搭建 1、创建项目1.1、创建Vue3/vite版Uniapp项目1.2、安装依赖1.3、运行项目2、弹出 用户隐私保护提示 方法2.1、更新用户隐私保护指引 和 修改配置文件2.2、授权结果处理方法3、修改`App.vue`文件内容4、处理报`[plugin:uni:mp-using-component…...
在CentOS中配置三个节点之间相互SSH免密登陆
在CentOS中配置三个节点(假设分别为node1、node2、node3)两两之间相互SSH免密登陆,可以按照以下步骤进行: 一、生成密钥对 在所有节点上生成密钥对: 在每个节点(node1、node2、node3)上执行以…...
arm 内联汇编基础
一、 Arm架构寄存器体系熟悉 基于arm neon 实现的代码有 intrinsic 和inline assembly 两种实现。 1.1 通用寄存器 arm v7 有 16 个 32-bit 通用寄存器,用 r0-r15 表示。 arm v8 有 31 个 64-bit 通用寄存器,用 x0-x30 表示,和 v7 不一样…...
Java语言程序设计——篇五(1)
数组 概述数组定义实例展示实战演练 二维数组定义数组元素的使用数组初始化器实战演练:矩阵计算 💫不规则二维数组实战演练:杨辉三角形 概述 ⚡️数组是相同数据类型的元素集合。各元素是有先后顺序的,它们在内存中按照这个先后顺…...
【香橙派开发板测试】:在黑科技Orange Pi AIpro部署YOLOv8深度学习纤维分割检测模型
文章目录 🚀🚀🚀前言一、1️⃣ Orange Pi AIpro开发板相关介绍1.1 🎓 核心配置1.2 ✨开发板接口详情图1.3 ⭐️开箱展示 二、2️⃣配置开发板详细教程2.1 🎓 烧录镜像系统2.2 ✨配置网络2.3 ⭐️使用SSH连接主板 三、…...
集成学习在数学建模中的应用
集成学习在数学建模中的应用 一、集成学习概述(一)基知(二)相关术语(三)集成学习为何能提高性能?(四)集成学习方法 二、Bagging方法(一)装袋&…...
WebKit 的 Web SQL 数据库:现代浏览器的本地存储解决方案
WebKit 的 Web SQL 数据库:现代浏览器的本地存储解决方案 随着Web应用的不断发展,对本地存储的需求也日益增加。WebKit作为许多现代浏览器的核心引擎,提供了一种强大的本地存储解决方案:Web SQL 数据库。本文将详细探讨Web SQL 数…...
Yolo-World网络模型结构及原理分析(三)——RepVL-PAN
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言1. 网络结构2. 特征融合3. 文本引导(Text-guided)4. 图像池化注意力(Image-Pooling Attention)5. 区域文本匹配&…...
代码随想录——一和零(Leetcode474)
题目链接 0-1背包 class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题m,n为背包两个维度// dp[i][j]:最多右i个0和j个1的strs的最大子集大小int[][] dp new int[m 1][n 1];// 遍历strs中字符串for(String str : strs){int num0 …...
力扣题解(组合总和IV)
377. 组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 思路: 本题实质上是给一些数字,让他们在满足和是targ…...
Postgresql主键自增的方法
Postgresql主键自增的方法 一.方法(一) 使用 serial PRIMARY KEY 插入数据 二.方法(二) 🎈边走、边悟🎈迟早会好 一.方法(一) 使用 serial PRIMARY KEY 建表语句如下…...
【源码阅读】Sony的go breaker熔断器源码探究
文章目录 背景源码分析总结 背景 在微服务时代,服务和服务之间调用、跨部门调用都是很常见的事,但这些调用都存在很多不确定因素,如核心服务A依赖的部门B服务挂掉了,那么A本身的功能将会受到直接的影响,而这些都会影响…...
LeetCode题(66,69,35,88)--《c++》
66.加一 // // Created by wxj05 on 2024/7/20. // //法一 class Solution { public:vector<int> plusOne(vector<int>& digits) {bool carry true; // 进位标志for (int i digits.size() - 1; i > 0 && carry; --i) {digits[i] 1;carry digit…...
来参与“向日葵杯”全国教育仿真技术大赛~
可点击进行了解:“向日葵杯”全国教育仿真技术大赛 (sunmooc.cn) 本次大赛共分为四个赛道:自主命题赛道、教育知识图谱设计赛道、FPGA硬件扑克牌对抗赛道、EasyAR元宇宙空间设计赛道。 参赛对象 : 具有正式学籍的在校研究生,本科…...
SQL每日一题:删除重复电子邮箱
题干 表: Person -------------------- | Column Name | Type | -------------------- | id | int | | email | varchar | -------------------- id 是该表的主键列(具有唯一值的列)。 该表的每一行包含一封电子邮件。电子邮件将不包含大写字母。 编写解决方案 删除 所有重复…...
3、宠物商店智能合约实战(truffle智能合约项目实战)
3、宠物商店智能合约实战(truffle智能合约项目实战) 1-宠物商店环境搭建、运行2-webjs与宠物逻辑实现3-领养智能合约初始化4-宠物领养实现5-更新宠物领养状态 1-宠物商店环境搭建、运行 https://www.trufflesuite.com/boxes/pet-shop 这个还是不行 或者…...
数据库系列
目录 一、数据库的概念和作用 1.数据库的特点 2.数据模型 二、数据库系统 1.数据库管理系统 2.数据库的基本操作 一、数据库的概念和作用 数据库是指长期存储在计算机内,有组织的、可共享的数据集合。它可视为一个电子化的文件柜,用来存储电子文件…...