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年的省…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
