【LCR 170. 交易逆序对的总数】

目录

  • 一、题目描述
  • 二、算法原理
  • 三、代码实现
    • 3.1升序:
    • 3.2降序:

一、题目描述

在这里插入图片描述

二、算法原理

在这里插入图片描述

三、代码实现

3.1升序:

class Solution 
{
public:int mergeSort(vector<int>& nums, int left, int right){if (left >= right){return 0;}int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//求一左一右vector<int> temp(right - left + 1);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] <= nums[cur2]){temp[i++] = nums[cur1++];}else{ret += (mid - cur1 + 1);temp[i++] = nums[cur2++];       }}while (cur1 <= mid) temp[i++] = nums[cur1++];while (cur2 <= right) temp[i++] = nums[cur2++];for (int i = left; i <= right; i++){nums[i] = temp[i - left];}return ret;}int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}
};

3.2降序:

class Solution 
{
public:int mergeSort(vector<int>& nums, int left, int right){if (left >= right){return 0;}int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//求一左一右vector<int> temp(right - left + 1);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] <= nums[cur2]){temp[i++] = nums[cur2++];}else{ret += (right-cur2+1);temp[i++] = nums[cur1++];       }}while (cur1 <= mid) temp[i++] = nums[cur1++];while (cur2 <= right) temp[i++] = nums[cur2++];for (int i = left; i <= right; i++){nums[i] = temp[i - left];}return ret;}int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166043.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mysql varchar int

年龄是数字类型int SELECT * FROM test ORDER BY age; 年龄是字符类型varchar SELECT * FROM test ORDER BY code; 第1种 补前导0可以和数字一样排序 MySQL会比较字符的ASCII值&#xff0c;并根据这些值来确定字符的排列顺序。 印象中oracle好像也是吧。 ASCII (American …

webgl计算包围盒大小

使用three.js&#xff1b; 代码&#xff1b; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>第一个three.js 示例</title><style>body {margin: 0;overflow: hidden;}</style><…

选择什么电容笔比较好?平板手写笔推荐

由于苹果Pencil的热销&#xff0c;让华国内市场上&#xff0c;也出现了不少的平替式电容笔&#xff0c;这些产品&#xff0c;有好有坏&#xff0c;价格也很公道。不过&#xff0c;也有很多产品的价格都很平价。我是一个拥有多年经验的数码发烧友&#xff0c;在前几年就开始用上…

【Django 04】Serialization 序列化的高级使用

序列化器 serializers 序列化器的作用 序列化将 queryset 和 instance 转换为 json/xml/yaml 返回给前端 反序列化与序列化则相反 定义序列化器 定义类&#xff0c;继承自 Serializer 通常新建一个 serializers.py 文件 撰写序列化内容 suah as 目前只支持 read_only 只…

IDEA 新版本设置菜单展开

使用了新版本的IDEA 新UI后&#xff0c;常用的file&#xff0c;view&#xff0c;菜单看不见了&#xff0c;不太适应&#xff0c;找了一下&#xff0c;有个配置可以修改。 打开settings里面把show main menu in a separate toolbar勾选上&#xff0c;应用保存就可以了

线性代数1:线性方程和系统

图片来自施泰德博物馆 Digital Collection (staedelmuseum.de) 一、前言 通过这些文章&#xff0c;我希望巩固我对这些基本概念的理解&#xff0c;同时如果可能的话&#xff0c;通过我希望成为一种基于直觉的数学学习方法为其他人提供额外的清晰度。如果有任何错误或机会需要我…

Java并发编程常见面试题总结

梳理Java并发编程相关的面试题&#xff0c;主要参考《JAVA并发编程实战》(Brian Goetz, Joshua Bloch, David Holmes, Tim Peierls, Joseph Bowbeer, Doug Lea 著, 韩锴, 方妙 译)一书&#xff0c;其余部分整合网络相关内容。注意&#xff0c;关于Java基础相关的面试题可以参考…

数据结构-树的概念结构及存储

&#x1f5e1;CSDN主页&#xff1a;d1ff1cult.&#x1f5e1; &#x1f5e1;代码云仓库&#xff1a;d1ff1cult.&#x1f5e1; &#x1f5e1;文章栏目&#xff1a;数据结构专栏&#x1f5e1; 目录 一、树的基本概念及结构 1树的概念 2树的存储 二、二叉树的概念及结构 1二叉树的概…

什么是t检验?

t检验&#xff08;t-test&#xff09;是一种统计方法&#xff0c;用于比较两组数据之间的平均值是否存在显著差异。它通常用于分析两组样本的平均值是否具有统计学上的显著性差异。t检验基于正态分布的假设&#xff0c;它计算两组数据之间的t值&#xff0c;然后通过与t分布表进…

Android笔记(七)Android JetPack Compose组件搭建Scaffold脚手架

在去年2022年曾发布一篇关于脚手架的文章&#xff1a;“Android JetPack Compose组件中Scaffold的应用” 。但是Android的版本从12变更到13及以上版本&#xff0c;导致一些细节的实现存在不同。在本文中&#xff0c;将从头开始介绍整个脚手架的搭建过程。 一、新建项目模块 在…

安装Docker

本安装教程参考Docker官方文档&#xff0c;地址如下&#xff1a;https://docs.docker.com/engine/install/centos/ 卸载旧版 首先如果系统中已经存在旧的Docker&#xff0c;则先卸载&#xff1a; yum remove docker \ docker-client \ docker-client-latest \ docker-common…

经典题型---旋转数组

经典题型—旋转数组 文章目录 经典题型---旋转数组一、题目二、代码实现 一、题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步…

Ubuntu系统下使用docker容器配置nginx并部署前端项目

1.下载 Nginx 镜像 命令 描述 docker pull nginx 下载最新版 Nginx 镜像 :2. 创建要挂载的宿主机目录 启动前需要先创建 Nginx 外部挂载的配置文件&#xff08; /home/nginx/conf/nginx.conf&#xff09; 之所以要先创建 , 是因为 Nginx 本身容器只存在 / etc/nginx 目录 ,…

识别准确率竟如此高,实时语音识别服务

前言 本文将介绍一个准确率非常高的语音识别框架&#xff0c;那就是FunASR&#xff0c;这个框架的模型训练数据超过几万个小时&#xff0c;经过测试&#xff0c;准确率非常高。本文将介绍如何启动WebSocket服务和Android调用这个服务来实时识别&#xff0c;一边说话一边出结果…

计算机毕业设计 基于SpringBoot智慧养老中心管理系统的设计与实现 Javaweb项目 Java实战项目 前后端分离 文档报告 代码讲解 安装调试

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…

C++:类的默认成员函数------构造函数析构函数(超详细解析,小白一看就懂!)

目录 一、前言 二、为什么会出现构造函数和析构函数 三、构造函数 &#x1f34e;构造函数的概念 &#x1f350;构造函数特性 &#x1f4a6;解释特性3&#xff1a;对象实例化时编译器自动调用对应的构造函数 &#x1f4a6;解释特性4&#xff1a;构造函数支持重载 &…

什么是大数据测试?有哪些类型?应该怎么测?

随着目前世界上各个国家使用大数据应用程序或应用大数据技术场景的数量呈指数增长&#xff0c;相应的&#xff0c;对于测试大数据应用时所需的知识与大数据测试工程师的需求也在同步增加。 针对大数据测试的相关技术已慢慢成为当下软件测试人员需要了解和掌握的一门通用技术。…

YOLOv5改进实战 | 更换主干网络Backbone(四)之轻量化模型MobileNetV3

前言 轻量化网络设计是一种针对移动设备等资源受限环境的深度学习模型设计方法。下面是一些常见的轻量化网络设计方法: 网络剪枝:移除神经网络中冗余的连接和参数,以达到模型压缩和加速的目的。分组卷积:将卷积操作分解为若干个较小的卷积操作,并将它们分别作用于输入的不…

JAVA基础(JAVA SE)学习笔记(六)面向对象编程(基础)

前言 1. 学习视频&#xff1a; 尚硅谷Java零基础全套视频教程(宋红康2023版&#xff0c;java入门自学必备)_哔哩哔哩_bilibili 2023最新Java学习路线 - 哔哩哔哩 第二阶段&#xff1a;Java面向对象编程 6.面向对象编程&#xff08;基础&#xff09; 7.面向对象编程&…

react-router-dom v6版本实现Tabs路由缓存切换

目录 文章目录 概要 效果 完整代码 概要 摆了半年摊&#xff0c;好久没写代码了&#xff0c;今天有人问我怎么实现React-Router-dom类似标签页缓存。后面看了一下router的官网。很久以前用的是react-router v5那个比较容易实现。v6变化挺大&#xff0c;但了解react的机制和rea…