交易逆序对的总数

题目链接

交易逆序对的总数

题目描述

注意点

  • 0 <= record.length <= 50000

解答思路

  • 本题是归并排序的扩展,可以先进入手撕归并排序了解
  • 利用归并排序进行合并时,对于左侧区间当前的首个元素leftNum,不论右侧区间当前的首个元素rightNum是否比leftNum大,只要右区间指针不在初始位置,说明右区间都有元素比leftNum小,leftNum对逆序对是有贡献的,具体贡献多少需要找到右区间所有比其小的元素数量,所以还需要继续移动右区间指针直到右区间首个元素比leftNum大或遍历完右区间为止,贡献值就是右区间指针从初始位置移动的步数

代码

class Solution {
    int res;
    public int reversePairs(int[] record) {
        res = 0;
        mergeSort(record, 0, record.length - 1);
        return res;
    }

    public int[] mergeSort(int[] record, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new int[] {record[left]};
        }
        int mid = (left + right) / 2;
        int len = right - left + 1;
        int[] leftArr = mergeSort(record, left, mid);
        int[] rightArr = mergeSort(record, mid + 1, right);
        int[] mergeArr = new int[len];
        int leftIdx = 0, rightIdx = 0;
        while (leftIdx < leftArr.length || rightIdx < rightArr.length) {
            // 左区间已遍历完,右区间数组后续值都比左区间大
            if (leftIdx >= leftArr.length) {
                mergeArr[leftIdx + rightIdx] = rightArr[rightIdx++];
                continue;
            }
            // 找到左区间比右区间哪些数更大
            while (rightIdx < rightArr.length && leftArr[leftIdx] > rightArr[rightIdx]) {
                mergeArr[leftIdx + rightIdx] = rightArr[rightIdx++];
            }
            mergeArr[leftIdx + rightIdx] = leftArr[leftIdx++];
            res += rightIdx;
        }
        return mergeArr;
    }
}

关键点

  • 归并排序的思想
  • 怎么通过归并的步骤找到某个元素对逆序对总数的贡献
  • 注意边界问题

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【智慧地球】星图地球 | 星图地球超算数据工场

当前空天信息处理涉及并发并行的大量计算问题&#xff0c;需要高性能计算、智能计算联合调度&#xff0c;以此来实现多算力融合&#xff1b;而我国算力产业规模快速增长&#xff0c;超算算力资源正需要以任务驱动来统筹。 基于此&#xff0c;中科星图与郑州中心展开紧密合作&a…

使用 Process Explorer 和 Windbg 排查软件线程堵塞案例分享

目录 1、问题说明 2、线程堵塞的可能原因分析 3、使用Windbg和Process Explorer确定线程中发生了死循环 4、根据Windbg中显示的函数调用堆栈去查看源码&#xff0c;找到问题 4.1、在Windbg定位发生死循环的函数的方法 4.2、在Windbg中查看变量的值去辅助分析 4.3、是循环…

抖店申请流程是什么?

我是电商珠珠 想要入驻抖店的人很多&#xff0c;但是知道流程的新手却没有几个。 从开店资料到入驻流程&#xff0c;我来具体的跟大家讲一讲。 第一个&#xff0c;新手开店资质 1、营业执照 营业执照是入驻门槛之一&#xff0c;营业执照类型分为两类&#xff0c;一类为企业…

快速批量运行命令

Ansible 是 redhat 提供的自动化运维工具&#xff0c;它是 Python编写&#xff0c;可以通过 pip 安装。 pip install ansible 它通过任务(task)、角色(role)、剧本(playbook) 组织工作项目&#xff0c;适用于批量化系统配置、软件部署等需要复杂操作的工作。 但对于批量运行命…

进程的程序替换(exec函数)【Linux】

进程的程序替换详解exec函数【Linux】 程序替换的原理exec系列函数函数理解命令理解&#xff08;助记&#xff09; 关于程序替换中环境变量的解释exec函数之间的关系exec函数的使用execlexeclpexecleexecv 程序替换的原理 进程的程序替换就是让子进程执行新程序&#xff0c; 执…

使用华为云鲲鹏弹性云服务器部署Discuz

本实验将在华为云鲲鹏弹性云服务器CentOS系统的实例上&#xff0c;部署Discuz!项目&#xff0c;并进行初步的安装测试。 注意&#xff1a;官网文档有些链接失效&#xff0c;本文在官方文档的基础上作出修改&#xff0c;具体参见Discuz安装这一步 操作前提&#xff1a;登录华为…

Android : 使用GestureDetector 进行手势识别—简单应用

示例图&#xff1a; GestureDetector 介绍&#xff1a; GestureDetector 是 Android 开发中用于识别和处理手势的一个类。它允许开发者检测用户在触摸屏上的各种手势&#xff0c;如滑动、长按、双击等。通过使用 GestureDetector&#xff0c;您可以轻松地为应用程序添加手势识…

FPGA设计时序约束十五、Set_Bus_Skew

目录 一、序言 二、Set Bus Skew 2.1 基本概念 2.2 设置界面 2.3 命令语法 2.4 报告分析 三、工程示例 3.1 工程代码 3.2 时序报告 四、参考资料 一、序言 在时序约束中&#xff0c;对时钟的约束除了set clock latency,set clock uncertainty,set input jitter外&…

蜥蜴目标检测数据集VOC格式1400张

蜥蜴&#xff0c;一种爬行动物&#xff0c;以其独特的形态和习性&#xff0c;成为了人们关注的焦点。 蜥蜴的外观多样&#xff0c;体型大小不一。它们通常拥有长条的身体、四肢和尾巴&#xff0c;鳞片覆盖全身&#xff0c;这使得它们能够在各种环境中轻松移动。大多数蜥蜴拥有…

在Ubuntu22.04上部署Stable Diffusion

在AI绘画软件领域Stable-Diffusion&#xff08;简称SD&#xff09;在开源领域绝对是不二之选&#xff0c;他的插件方式可以让此软件具有更多的功能&#xff0c;开发者社群为此提供了大量免费高质量的外接预训练模型&#xff08;fine-tune&#xff09;和插件&#xff0c;并持续维…

力扣-42.接雨水

题目&#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组[0,1,0,2…

day06、SQL语言之概述

SQl 语言之概述 6.1 SQL语言概述6.2 SQL语言之DDL定义数据库6.3 SQL语言之DML操纵数据库 6.1 SQL语言概述 6.2 SQL语言之DDL定义数据库 6.3 SQL语言之DML操纵数据库

mysql死锁排查

查看正在进行中的事务 SELECT * FROM information_schema.INNODB_TRX;字段解释trx_id唯一事务id号&#xff0c;只读事务和非锁事务是不会创建id的trx_state事务的执行状态&#xff0c;值一般分为&#xff1a;RUNNING, LOCK WAIT, ROLLING BACK, and COMMITTING.trx_started事务…

智能手机2024:狂卷“微创新”后如何突破新机遇

文 | 智能相对论 作者 | 楷楷 2023年&#xff0c;智能手机市场终于开始展露曙光。Counterpoint Research数据显示&#xff0c;2023年10月全球智能手机销量同比增长5%&#xff0c;智能手机市场出货量在经历了连续27个月的同比下滑后&#xff0c;首次出现同比正增长。 特别是在…

Redis学习笔记(1)——感谢尚硅谷官方文档

Redis学习笔记&#xff08;1&#xff09;——感谢尚硅谷官方文档 1. NoSQL1.1 NoSQL数据库概述1.2 各种NoSQL数据库 2. Redis数据库安装2.1 安装条件2.2 Widows下如何安装Redis?2.3 Linux下如何安装Redis? 3. Redis介绍3.1 Redis 简介3.2 Redis 优势3.3 Redis与其他key-value…

深入理解CRON表达式:时间调度的艺术

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

three.js相机按照指定路线在建筑模型中漫游(支持开始,暂停)

three.js相机按照指定路线在模型中漫游&#xff08;支持开始&#xff0c;暂停&#xff09; 关键点 相机运动曲线 // 相机路线 const points [new THREE.Vector3(0, 40, 300),new THREE.Vector3(50, 40, 300),new THREE.Vector3(50, 40, 50),new THREE.Vector3(150, 40, 50),…

集群渲染是?渲染农场是?两者与云渲染关联是什么

在数字化浪潮不断推进的当下&#xff0c;渲染技术在多个行业中发挥着至关重要的作用&#xff0c;尤其体现在电影制作、建筑可视化以及电子游戏开发等领域。在众多渲染技术中&#xff0c;集群渲染、渲染农场以及云渲染特别受到业界的重视。本文旨在阐述这些概念的含义以及它们之…

Web 自动化测试过程中会遇到哪些问题?

作者&#xff1a;木可 链接&#xff1a;https://www.zhihu.com/question/636965892/answer/3341410674 来源&#xff1a;知乎 著作权归作者所有。商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处。 Web自动化是指使用测试脚本来自动执行网页上的任务。这包括填…

vue3安装vue-tools

https://github.com/vuejs/devtools/tree/v6.5.0/packages 打开浏览器扩展程序 这个文件直接拖进扩展程序