当前位置: 首页 > news >正文

分治-归并排序-逆序对问题

目录

1.升序(以右边的合并组为基准)

2.降序(以左边的合并组为基准)

 3.逆对序--固定下标

1.升序(以右边的合并组为基准)

找出左边有多少个数比我(nums[right])大

  • 应该在每一次合并之前,进行逆序对查找
  • 每一个该合并的组都是按升序排列,所以当nums[left]<nums[right]时,应该left++,因为都是升序,所以当nums[left]>nums[right],right++时,left从当前位置不动。

class Solution {
public:vector<int> ret;int vim=0;int reversePairs(vector<int>& record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1, i=0;while(left<=mid&&right<=high){if(nums[left]<=nums[right]) ret[i++]=nums[left++];else  {ret[i++]=nums[right++];vim+=(mid+1-left);}}while(left<=mid) ret[i++]=nums[left++];while(right<=high) ret[i++]=nums[right++];for(int i=0;i<high-low+1;i++){nums[i+low]=ret[i];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return;int mid=(low+high)/2;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};

2.降序(以左边的合并组为基准)

 找出多少个数比我小

 合并过程:

 

class Solution {
public:vector<int> ret;int vim=0;int reversePairs(vector<int>& record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1, i=0;while(left<=mid&&right<=high){if(nums[left]>nums[right]) {vim+=(high-right+1);ret[i++]=nums[left++];}else  {ret[i++]=nums[right++];}}while(left<=mid) ret[i++]=nums[left++];while(right<=high) ret[i++]=nums[right++];for(int i=0;i<high-low+1;i++){nums[i+low]=ret[i];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return;int mid=(low+high)/2;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};

 对比:

降序升序

void merge(vector<int>&nums,int low,int high,int mid)
    {
        int left=low,right=mid+1, i=0;
        while(left<=mid&&right<=high)
        {
             if(nums[left]>nums[right]) 
             {
                vim+=(high-right+1);
                ret[i++]=nums[left++];
             }
            else  
             ret[i++]=nums[right++];

}
        while(left<=mid) ret[i++]=nums[left++];
        while(right<=high) ret[i++]=nums[right++];
        for(int i=0;i<high-low+1;i++)
        {
            nums[i+low]=ret[i];
        }
    }

 void merge(vector<int>&nums,int low,int high,int mid)
    {
        int left=low,right=mid+1, i=0;
        while(left<=mid&&right<=high)
        {
             if(nums[left]<=nums[right])                 ret[i++]=nums[left++];
            else  
            {
                ret[i++]=nums[right++];
                vim+=(mid+1-left);
            }

        }
        while(left<=mid) ret[i++]=nums[left++];
        while(right<=high) ret[i++]=nums[right++];
        for(int i=0;i<high-low+1;i++)
        {
            nums[i+low]=ret[i];
        }
    }

 3.逆对序--固定下标

增加一个下标数据,和交换下标数组,当交换数组发生数据交换时,交换下标数组也要发生数据交换

 

class Solution {vector<int> tempnums,index,tempindex,count;
public:vector<int> countSmaller(vector<int>& nums) {int n=nums.size();tempnums.resize(n);//交换数组tempindex.resize(n);//交换下标index.resize(n);//存放原始下表count.resize(n);//存放结果for(int i=0;i<n;i++) index[i]=i;mergesort(nums,0,n-1);return count;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1,i=0;while(left<=mid&&right<=high){if(nums[left]>nums[right]) {tempnums[i]=nums[left];tempindex[i]=index[left];count[index[left]]+=(high-right+1);i++;left++;}else{tempindex[i]=index[right];tempnums[i]=nums[right];i++;right++;}}while(left<=mid){tempnums[i]=nums[left];tempindex[i]=index[left];i++;left++;}while(right<=high){tempindex[i]=index[right];tempnums[i]=nums[right];i++;right++;}for(int j=0;j<i;j++){nums[j+low]=tempnums[j];index[j+low]=tempindex[j];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return ;int mid=(low+high)>>1;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};

相关文章:

分治-归并排序-逆序对问题

目录 1.升序&#xff08;以右边的合并组为基准&#xff09; 2.降序&#xff08;以左边的合并组为基准&#xff09; 3.逆对序--固定下标 1.升序&#xff08;以右边的合并组为基准&#xff09; 找出左边有多少个数比我(nums[right])大 应该在每一次合并之前&#xff0c;进行…...

mysql-getshell的几种方法

mysql_getshell的几种方法 mysql_getshell 一、mysql的–os-shell 利用原理 –os-shell就是使用udf提权获取WebShell。也是通过into oufile向服务器写入两个文件&#xff0c;一个可以直接执行系统命令&#xff0c;一个进行上传文件。此为sqlmap的一个命令&#xff0c;利用这…...

初阶数据结构--树

1. 树的概念与结构 树是⼀种⾮线性的数据结构&#xff0c;它是由 n&#xff08;n>0&#xff09; 个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;⽽叶朝下的。 有⼀个特殊的结点&#xff0c;称…...

搭建redis主从同步实现读写分离(原理剖析)

搭建redis主从同步实现读写分离(原理剖析) 文章目录 搭建redis主从同步实现读写分离(原理剖析)前言一、搭建主从同步二、同步原理 前言 为什么要学习redis主从同步&#xff0c;实现读写分析。因为单机的redis虽然是基于内存&#xff0c;单机并发已经能支撑很高。但是随着业务量…...

Python3 学习笔记

Python3 简介 | 菜鸟教程 一 Python3 简介 Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具有很强的可读性&#xff0c;相比其他语言经常使用英文关键字&#xff0c;其他语言的一些标点符号&#xff0c;它具有比其他语言更有特色…...

kmpmanacher

KMP 理论 KMP算法的核心是构建一个部分匹配表&#xff0c;也称为前缀表。这个表记录了模式串中每个位置之前的最长公共前缀和后缀的长度。例如&#xff0c;对于模式串"ababaca"&#xff0c;其部分匹配表如下&#xff1a; 位置0123456字符ababaca最长公共前后缀长度…...

ts基础知识总结

TypeScript&#xff08;简称TS&#xff09;是JavaScript&#xff08;简称JS&#xff09;的一个超集&#xff0c;它在JS的基础上增加了静态类型检查、类、模块等特性。 TypeScript 与 JavaScript 的不同及好处 不同点 类型系统 JavaScript 是一种弱类型语言&#xff0c;这意味…...

操作系统内存管理

为什么要有虚拟内存 单片机的CPU直接操作内存的物理地址&#xff0c;这就导致在内存中同时运行两个程序是不可能的&#xff0c;有可能会出现第一个程序在2000的位置写入新的值将会擦掉第二个程序存放在相同位置上的内容。 出现这个问题的根本原因是两个程序引用了绝对物理地址。…...

M芯片,能运行普通应用程序的原架构虚拟机

在我们使用搭载了Apple芯片的Mac时,很多时候会用到windows虚拟机来使用windows应用程序 但是Apple芯片是ARM架构,如果运行原价构的虚拟机,很多64位的普通应用程序就无法运行,如果使用UTM来安装64位的跨架构虚拟机,就会非常卡慢 但实际上使用一种特殊的系统镜像,就可以使用ARM…...

多功能指示牌的主要功能有哪些?

哇哦&#xff01;咱们的多功能指示牌可有着超多超厉害的主要功能哦&#xff0c;简直就是生活中的超级小助手&#xff0c;涵盖了方方面面呢&#xff01; 指示导向功能 道路指引&#xff1a;不管是在繁华热闹的城市道路&#xff0c;还是车水马龙的高速公路&#xff0c;亦或是风…...

Superset 问题

和nginx结合使用&#xff0c;如果不是配置到根路径&#xff0c;会比较麻烦&#xff0c;我试了很多种方法&#xff0c;也就 这个 靠谱点&#xff0c;不过&#xff0c;我最后还是选择的部署在根路径&#xff0c;先探索一番再说默认不能选择mysql数据库&#xff0c;需要安装mysql客…...

安装gpu版本的dgl

1.先去网址&#xff0c;找到对应版本的dgl,然后下载到本地。 dgl-whl下载地址 我的是python 3.8 &#xff0c;cuda 11.6. windows 2.在虚拟环境里 输入 pip install E:\dgl-1.0.2cu116-cp38-cp38-win_amd64.whl &#xff08;因为我下载到E盘里了&#xff09; 这样GPU版本的d…...

vue watch和 watchEffect

在 Vue 3 中&#xff0c;watch 和 watchEffect 是两个用于响应式地监听数据变化并执行副作用的 API。它们在功能上有一些相似之处&#xff0c;但用途和行为有所不同。以下是对 watch 和 watchEffect 的详细对比和解释&#xff1a; 1. watch watch 是一个更通用的 API&#xf…...

JavaScript基础--03-变量的数据类型:基本数据类型和引用数据类型

JavaScript基础--03-变量的数据类型&#xff1a;基本数据类型和引用数据类型 前言变量的数据类型为什么需要数据类型JS中一共有六种数据类型 一个经典的例子栈内存和堆内存 前言 我们接着上一篇文章 JavaScript基础–02-变量 来讲。 下一篇文章 JavaScript基础–04-基本数据类…...

WindowsPE文件格式入门05.PE加载器LoadPE

https://bpsend.net/thread-316-1-1.html LoadPE - pe 加载器 壳的前身 如果想访问一个程序运行起来的内存,一种方法就是跨进程读写内存,但是跨进程读写内存需要来回调用api,不如直接访问地址来得方便,那么如果我们需要直接访问地址,该怎么做呢?.需要把dll注进程,注进去的代码…...

【Redis】通用命令

使用者通过redis-cli客户端和redis服务器交互&#xff0c;涉及到很多的redis命令&#xff0c;redis的命令非常多&#xff0c;我们需要多练习常用的命令&#xff0c;以及学会使用redis的文档。 一、get和set命令&#xff08;最核心的命令&#xff09; Redis中最核心的两个命令&…...

Android学习总结之service篇

引言 在 Android 开发里&#xff0c;Service 与 IntentService 是非常关键的组件&#xff0c;它们能够让应用在后台开展长时间运行的操作。不过&#xff0c;很多开发者仅仅停留在使用这两个组件的层面&#xff0c;对其内部的源码实现了解甚少。本文将深入剖析 Service 和 Inte…...

基于CATIA产品结构树智能排序的二次开发技术解析——深度定制BOM层级管理系统的Pycatia实践

引言 在航空制造与汽车装配领域&#xff0c;CATIA产品结构树&#xff08;Product Tree&#xff09;的规范性直接影响MBOM管理效率。传统手动排序存在两大痛点&#xff1a; ​多级编号混乱&#xff1a;混合零件号&#xff08;PartNumber&#xff09;与实例名&#xff08;Insta…...

机器人轨迹跟踪控制——CLF-CBF-QP

本次使用MATLAB复现CLF-CBF-QP算法,以实现机器人轨迹跟踪同时保证安全性能 模型 使用自行车模型来进行模拟机器人的移动动态,具体的模型推导参考车辆运动学模型-自行车模型 采用偏差变量 p ~ = p − p r e f u ~ = u − u r e f \tilde{p} = p - p_{ref} \\ \tilde{u} = …...

道路裂缝数据集CrackForest-156-labelme

来源于开源的数据集 https://github.com/cuilimeng/CrackForest-dataset 进行整理修改而成。 文章目录 1. 介绍2. 数据文件3. 应用场景4. 相关工具5. 下载地址 1. 介绍 在现代城市管理中&#xff0c;道路状况的监测与维护是确保交通安全和城市基础设施健康的重要环节。 CrackF…...

数据定义语言

一、DDL的核心功能 DDL用于定义和管理数据库对象的结构,包括数据库、表、索引、视图等,主要操作包括创建、修改、删除。其核心命令包括: CREATE:创建对象(数据库、表、索引等) ALTER:修改对象结构(如添加/删除列) DROP:删除对象 TRUNCATE:清空表数据(保留结构) RE…...

爬楼梯问题-动态规划

一、题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 方法1. 1 阶 1 阶 方法2. 2 阶…...

MySQL篇(四)事务相关知识详解

MySQL篇(四&#xff09;事务相关知识详解 MySQL篇(四&#xff09;事务相关知识详解一、事务的特性&#xff08;ACID&#xff09;原子性&#xff08;Atomicity&#xff09;一致性&#xff08;Consistency&#xff09;隔离性&#xff08;Isolation&#xff09;持久性&#xff08;…...

C++第14届蓝桥杯b组学习笔记

1. 日期统计 小蓝现在有一个长度为 100100 的数组&#xff0c;数组中的每个元素的值都在 00 到 99 的范围之内。数组中的元素从左至右如下所示&#xff1a; 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4…...

4.5蓝桥杯|高塔登顶方案(5025)

作者语录&#xff1a; 1、 从不会做到会做的过程&#xff0c;从不理解到不理解的过程&#xff0c;从一个不会做这道题的人的角度出发看这个问题&#xff0c;好命苦嗷嗷嗷&#xff01; 2、只有我受煎熬吗&#xff0c;偶买噶&#xff0c;&#xff0c;&#xff0c; 目录 研究步骤…...

[MySQL初阶]MySQL(9)事务机制

标题&#xff1a;[MySQL初阶]MySQL&#xff08;9&#xff09;事物机制 水墨不写bug 文章目录 一、认识事务1、多线程访问数据库出现的问题2、对CURD的限制是通过事务机制实现的3、事务的四个属性4、哪些引擎支持事务 二、事务的提交与autocommit设置三、事务的隔离性和隔离级别…...

3535 数组分割

3535 数组分割 ⭐️难度&#xff1a;困难 &#x1f31f;考点&#xff1a;2023、省赛、动态规划 &#x1f4d6; &#x1f4da; import java.util.*;public class Main {static int MOD 1000000007;static int N 1005;public static void main(String[] args) {Scanner sc …...

线程池的工作原理

固定线程池&#xff1a;线程池中的线程数是固定的&#xff0c;线程池创建时就已经设定了固定的线程数量。在任务提交时&#xff0c;线程池会将任务分配给空闲的线程执行。如果所有线程都在执行任务&#xff0c;新的任务会被放到任务队列中&#xff0c;直到有线程空闲出来。 线…...

论文导读 | SOSP23 | Gemini:大模型 内存CheckPoint 快速故障恢复

本期分享的是一篇SOSP 2023论文&#xff1a; Gemini: Fast Failure Recovery in Distributed Training with In-Memory Checkpoints Zhuang Wang (Rice University), Zhen Jia (Amazon Web Services, Inc.), Shuai Zheng (Amazon Web Services), Zhen Zhang (Amazon Web Servic…...

windows 常用命令总结

工作中用到的 Linux 总结&#xff08;持续更新中...&#xff09;_linux工作经验-CSDN博客 PS&#xff1a; 推荐使用 powershell 而不是 cmd&#xff0c;因为PowerShell 是一个更先进和功能更强大的工具&#xff08; powershell 有命令记忆功能&#xff0c;比较方便&#xff09…...

【Linux】进程间通信、匿名管道、进程池

一.什么是通信 进程间通信(Inter-Process Communication&#xff0c;IPC),是指在操作系统中&#xff0c;不同进程之间进行数据交换和同步的机制。由于每个进程通常拥有独立的内存空间&#xff0c;进程间无法直接访问对方的内存&#xff0c;因此需要通过特定的机制来实现通信和…...

【Block总结】PlainUSR的局部注意力,即插即用|ACCV2024

论文信息 标题: PlainUSR: Chasing Faster ConvNet for Efficient Super-Resolution作者: Yan Wang, Yusen Li, Gang Wang, Xiaoguang Liu发表时间: 2024年会议/期刊: 亚洲计算机视觉会议&#xff08;ACCV 2024&#xff09;研究背景: 超分辨率&#xff08;Super-Resolution, S…...

35信号和槽_信号槽小结

Qt 信号槽 1.信号槽是啥~~ 尤其是和 Linux 中的信号进行了对比&#xff08;三要素&#xff09; 1) 信号源 2) 信号的类型 3)信号的处理方式 2.信号槽 使用 connect 3.如何查阅文档. 一个控件&#xff0c;内置了哪些信号&#xff0c;信号都是何时触发 一…...

现代复古电影海报品牌徽标设计衬线英文字体安装包 Thick – Retro Vintage Cinematic Font

Thick 是一种大胆的复古字体&#xff0c;专为有影响力的标题和怀旧的视觉效果而设计。其厚实的字体、复古魅力和电影风格使其成为电影海报、产品标签、活动品牌和编辑设计的理想选择。无论您是在引导电影的黄金时代&#xff0c;还是在现代布局中注入复古活力&#xff0c;Thick …...

低代码开发平台:飞帆画 echarts 柱状图

https://fvi.cn/711 柱状图这个控件是由折线图的控件改过来的&#xff0c;在配置中&#xff0c;单选框选择柱状图就行了。...

Linux中C++ gdb调试命令

编译可执行文件需要带上-g选项参数 输入回车则重复执行上一次命令&#xff1b; 进入gdb&#xff1a; gdb 程序名运行gdb命令&#xff1a; r打断点命令&#xff1a; b 行号查看断点命令&#xff1a; i b打印变量命令&#xff1a; p 变量名持续查看变量命令&#xff1a; d…...

Python精进系列:从 __name__ 开始了解 python 常见内置变量

目录 引言一、__name__是什么&#xff1f;案例1&#xff1a;直接运行模块案例2&#xff1a;模块被导入 二、__name__的主要用途&#xff08;一&#xff09;区分主程序和导入模块案例3&#xff1a;测试代码隔离&#xff08;二&#xff09;动态导入模块案例4&#xff1a;根据环境…...

Nacos 服务发现的核心模型有哪些?Service, Instance, Cluster 之间的关系是什么?

Nacos 服务发现的核心模型 Nacos 服务发现的核心数据模型主要围绕以下几个关键概念构建&#xff0c;它们共同构成了服务注册与发现的基础&#xff1a; Namespace (命名空间): 用途: 用于进行环境隔离。比如&#xff0c;你可以为开发环境 (dev)、测试环境 (test) 和生产环境 (p…...

Java程序设计第1章:概述

一、Hello World 1.代码&#xff1a; public class HelloWorld {public static void main(String[] args){System.out.println("Hello World!");} } 2.运行结果&#xff1a; Hello World! 二、输出姓名、学号、班级 1.题目&#xff1a; 编写一个Application&a…...

C++开发工具全景指南

专业编译与调试工具深度解析 2025年4月 编译器套件 GNU Compiler Collection (GCC) GNU编译器套件是自由软件基金会开发的跨平台编译器系统&#xff0c;支持C、C、Objective-C、Fortran、Ada等多种编程语言。作为Linux系统的标准编译器&#xff0c;GCC以其强大的优化能力和…...

Java的Selenium的特殊元素操作与定位之iframe切换

iframe切换 四种切换方式: driver.switchTo().frame(index);driver.switchTo().frame(id);driver.switchTo().frame(name);driver.switchTo().frame(WebElement); 切换之后&#xff0c;回到默认内容页面(否则会找不到元素 driver.switchTo().defaultContent(); //iframe处…...

AI比人脑更强,因为被植入思维模型【42】思维投影思维模型

giszz的理解&#xff1a;本质和外在。我们的行为举止&#xff0c;都是我们的内心的表现。从外边可以看内心&#xff0c;从内心可以判断外在。曾国藩有&#xff17;个识人的方法&#xff0c;大部分的人在他的面前如同没穿衣服一样。对于我们自身的启迪&#xff0c;我认为有四点&…...

7-12 最长对称子串(PTA)

对给定的字符串&#xff0c;本题要求你输出最长对称子串的长度。例如&#xff0c;给定Is PAT&TAP symmetric?&#xff0c;最长对称子串为s PAT&TAP s&#xff0c;于是你应该输出11。 输入格式&#xff1a; 输入在一行中给出长度不超过1000的非空字符串。 输出格式&…...

嵌入式AI的本地化部署的好处

嵌入式AI本地化处理&#xff08;即边缘计算&#xff09;的核心优势在于将AI算力下沉至设备端&#xff0c;直接处理数据而非依赖云端&#xff0c;这种模式在多个维度上展现出显著价值&#xff1a; 一、数据隐私与安全性提升 1. 敏感数据本地存储 金融、医疗等涉及隐私的行业…...

0基础 | 硬件 | 电源系统 一

降压电路LDO 几乎所有LDO都是基于此拓扑结构 图 拓扑结构 LDO属于线性电源&#xff0c;通过控制开关管的导通程度实现稳压&#xff0c;输出纹波小&#xff0c;无开关噪声 线性电源&#xff0c;IoutIin&#xff0c;发热功率P电压差△U*电流I&#xff0c;转换效率Vo/Vi LDO不适…...

LeetCode详解之如何一步步优化到最佳解法:20. 有效的括号

LeetCode详解系列的总目录&#xff08;持续更新中&#xff09;&#xff1a; LeetCode详解之如何一步步优化到最佳解法&#xff1a;前100题目录&#xff08;更新中...&#xff09;-CSDN博客 LeetCode详解系列的上一题链接&#xff1a; LeetCode详解之如何一步步优化到最佳解法…...

LeetCode18四数之和

代码来源&#xff1a;代码随想录 /*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/ int com…...

《K230 从熟悉到...》无线网络

《K230 从熟悉到...》无线网络 STA模式 《庐山派 K230 从熟悉到...》无线网络 无线网络中通常是STA&#xff08;Station&#xff0c;站点&#xff09;和AP&#xff08;Access Point&#xff0c;无线接入点&#xff09;。 STA&#xff08;站点&#xff09; 定义&#xff1a;STA…...

去中心化指数(链上ETF)

去中心化指数&#xff08;链上ETF&#xff09; 核心概念 去中心化指数&#xff1a; 类似传统金融的ETF&#xff08;交易所交易基金&#xff09;&#xff0c;通过一篮子代币分散投资风险&#xff0c;无需主动管理。 核心价值&#xff1a;降低研究成本、分散风险、自动化资产…...

LeeCode题库第1695题

项目场景&#xff1a; 给你一个正整数数组 nums &#xff0c;请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。 返回 只删除一个 子数组可获得的 最大得分 。 如果数组 b 是数组 a 的一个连续子序列&#xff0c;即如果它等于 a[l],…...