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年的省…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
