分治_归并_归并排序(逆序对)

912. 排序数组

上一次我们做这道题时用的是数组划分三块的思想搭配随机选择基准元素的⽅法。

随机选择一个数，以这个数key为基准划分数组，小于key的数在左边，大于key的数在右边。再把被划分的两部份再找key值划分，直到只剩1或者0个元素返回。

遍历完最后一层该数组就排序完成

接下来我们采用归并的思想来做。

1.以中间点mid把数组分为两部份

2.一直划分直到 到最后一层只剩一个元素或者没有元素返回

3.之下而上返回时，要对左右两部份数组进行排序。借助一个临时数组 两个指针分别指向两个数组，由小到大排，先把小的放里面。再把临时数组排好的内容写回原数组。

4.以此类推，直到返回最上层，合并完左右两个有序数组，排序完成。

归并排序递归实现过程就像二叉树的后续遍历。

class Solution {vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);return tmp;}void mergeSort(vector<int>&nums,int left,int right){if(left>=right) return;//1.选择中间点划分区域int mid=(left+right)>>1;//2.把左右区间排序mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//3.合并两个有序数组int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right)tmp[i++]=nums[cur1]<nums[cur2]?nums[cur1++]:nums[cur2++];//合并剩余元素while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];//将tmp中排好序的数字写回numsfor(int i=left;i<=right;i++)nums[i]=tmp[i-left];}
};

1.借助临时数组时，最好把它定义成全局变量，提前申请好空间，提高效率。

2.合并左右两数组时，可能有一方数组提前结束，后面还需要把另一个数组的剩余部分元素继续合并。

3.int mid=(left+right)>>1表示/2。如果数据溢出可以mid=left+(right-left)/2

LCR 170. 交易逆序对的总数

逆序对，第一个数>第二个数 且第一个数在数组的位置要在第二个数前面。

方法：归并

1.从一个数组中找逆序对，我们把该数组分为两半，左边部分和右半部分。

那逆序对的个数=左半部分逆序对的个数+右半部分逆序对的个数+左边取一个数和右边取一个数组成的逆序对的个数。

2.如果我们再计算完左右部分内逆序对的个数后，对左右部分内进行排序，一左一右的逆序对个数会改变吗？不会，因为左右两个数的相对位置没有改变，左半部分数仍在右半部分数的前面。一左一右挑完逆序对后，排序也不影响。

所以 总数=左半部分+排序 +右半部分+排序 +一左一右+排序 

3.利用归并。算一个数组的逆序对个数，先把它分为左右两部份。求左部分的个数，是不是也可以把它再分为左右两部分，直到分到只剩1 0个元素 逆序对个数就为0。这和归并排序的规律是不是很像呢？

所以在递归过程中我们就可以把左右两部分的个数算出来。想一想，如果第一次原数组，分为左右部分，左部分的个数=它的左部分+它的右部分+它的一左一右。因此，我们只要算出一左一右的个数，第一层左部分 右部分的个数在递归中就可以算出来。

4.怎么算一左一右的个数？

首先为什么要排序呢？因为，当左右部分内排完序 左右部分都是升序/降序，进行归并时 当我们固定cur2 只要算出在左部分有多少个大于cur2的数就可以了。

策略一:找出该数前，有多少个数比我大

先来看升序时归并的代码，我们先规定cur2不动，找左部分大于cur2的个数。cur1++直到cur1>cur2，个数就为mid-cur1+1 (cur1右边)，最后cur2++ 继续找。

1.nums[cur1]<=nums[cur2] cur1++;

2.nums[cur1]>nums[cur2]  re+=mid-cur1+1; cur2++;

但我们反过来，先固定cur1不动，让cur2找比cur1小的个数。cur2++直到cur2>cur1，个数为cur2-(mid+1)+1 (cur2左边) ，最后cur1++ cur2++继续找。但cur2向右移，等再找到时，cur2左边的个数就包含的上一次找到的个数，就会重复。所以 升序时要先固定cur2

        while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur1++];else {re+=mid-cur1+1;//cur1右边个数tmp[i++]=nums[cur2++];}}

策略二:当前元素的后面，有多少个元素比我小

降序也可以完成，不过我们先规定cur1不动，找右部分小于cur1的个数。cur2++直到cur2<cur1，个数就为right-cur2+1 (cur2右边)，最后cur1++ 换下一个位置 继续找。

1.nums[cur1]<=nums[cur2] cur2++;

2.nums[cur1]>nums[cur2]  re+=right-cur2+1; cur1++;

        while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur2++];else {re+=right-cur2+1;//cur2右边的个数tmp[i++]=nums[cur1++];}}

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return Sort(record,0,record.size()-1);}int Sort(vector<int>&nums,int left,int right){int re=0;if(left>=right) return 0;//1.找中间数，把数组分为两半int mid=(left+right)>>1;//2.左边的个数+排序 右边的个数+排序re+=Sort(nums,left,mid);re+=Sort(nums,mid+1,right);//3.一左一右的个数 (升序)int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur1++];else {re+=mid-cur1+1;tmp[i++]=nums[cur2++];}}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];for(int i=left;i<=right;i++)nums[i]=tmp[i-left];return re;}
};

315. 计算右侧小于当前元素的个数

这道题也是算逆序对的个数，不过 上一道是算逆序对总数。这道是算在该下标下后面的数中可以组成逆序对的个数。

在排序中会把元素的下标改变，所以我们要有一个数组index记录元素在原数组的下标，并在排序过程中随着的元素同步改变 保证能找到该元素在原数组的下标。

我们以降序为基础，cur1固定 cur2++找cur2<cur1，right-cur2+1(cur2右边)的数就是可以和cur1组成逆序对的数，再根据index映射到cur1在原数组的下标。

class Solution {vector<int> tmp;vector<int> tmp2;vector<int> index;vector<int> re;
public:vector<int> countSmaller(vector<int>& nums) {int n=nums.size();re.resize(n);tmp.resize(n);tmp2.resize(n);index.resize(n);for(int i=0;i<n;i++) index[i]=i;sort(nums,0,n-1);return re;}void sort(vector<int>&nums,int left,int right){if(left>=right) return;int mid=(right-left)/2+left;sort(nums,left,mid);sort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]){tmp2[i]=index[cur2];tmp[i++]=index[cur2++];}else {re[index[cur1]]+=right-cur2+1;tmp2[i]=index[cur1];tmp[i++]=nums[cur1++];}}while(cur1<=mid){tmp2[i]=index[cur1];tmp[i++]=nums[cur1++];}while(cur2<=right){tmp2[i]=index[cur2];tmp[i++]=nums[cur2++];}for(int i=left;i<=right;i++){nums[i]=tmp[i-left];index[i]=tmp2[i-left];}}
};

1.数组降序排序

2.index数组建立元素和它在原数组的下标的映射

3.index数组中的对应元素要在nums元素改变位置时同步改变

4.re[index[cur1]]+=right-cur2+1; 

index[cur1]因为是固定cur1不动，进行映射时要找cur1

+= 在向上递归时 不断在合并的右数组中找逆序对

493. 翻转对

这道和找逆序对总个数的题不同的是，[n,m]前面n较大的值要>后面n小的值的2倍。

原本是n>m就可以了，这会导致无法在排序时一起找出翻转对。

1.我们要在排序前，利用单调性先找出翻转对的个数

2.再进行排序并合并 进行递归

依旧是把数组以中间点mid分为左右两部份，cur1 cur2分别指向左右部分。

1.降序 cur1固定 cur2++ 找cur2*2<cur1的点  re+=rgiht-cur2+1（cur2右边）

2.升序 cur2固定 cur1++ 找cur1/2>cur2的点 re+=mid-cur1+1（cur1右边）

降序 注意nums[cur2]*2时会出现整数溢出，可以选择用中间变量long long存取后再比较。

或者判断条件nums[cur1]<=nums[cur2]*2两边都除2.0 -> nums[cur1]/2.0<=nums[cur2]

为什么除2.0 而不是2？因为除整型2会除不尽

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& nums) {int n=nums.size();tmp.resize(n);return sort(nums,0,nums.size()-1);}int sort(vector<int>&nums,int left,int right){if(left>=right) return 0;int re=0;int mid=(left+right)>>1;re+=sort(nums,left,mid);re+=sort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){long long c2=nums[cur2];c2*=2;if(nums[cur1]<=c2){cur2++;}else{re+=right-cur2+1;cur1++;}}        cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]){tmp[i++]=nums[cur2++];}else{tmp[i++]=nums[cur1++];}}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];for(int i=left;i<=right;i++){nums[i]=tmp[i-left];}return re;}
};

升序 改变cur1 cur2顺序就可以

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& nums) {int n=nums.size();tmp.resize(n);return sort(nums,0,nums.size()-1);}int sort(vector<int>&nums,int left,int right){if(left>=right) return 0;int re=0;int mid=(left+right)>>1;re+=sort(nums,left,mid);re+=sort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]/2.0<=nums[cur2]){cur1++;}else{re+=mid-cur1+1;cur2++;}}        cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]){tmp[i++]=nums[cur1++];}else{tmp[i++]=nums[cur2++];}}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];for(int i=left;i<=right;i++){nums[i]=tmp[i-left];}return re;}
};

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

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

相关文章

环境兼容： Vue3+ELement-plus

环境兼容： Vue3+ELement-plus

题目&#xff1a;环境兼容&#xff1a; Vue3ELement-plus 前言 身为小白的我也在负责一个项目咯&#xff0c;开发的是Vue3项目&#xff0c;然后就搜阅多篇文章&#xff0c;整理了这个。内容很多是转载的&#xff0c;拼成的我这个文章。 Element-plus简介 Element-plus 是基于…
阅读更多...
UE5基本数据类型

UE5基本数据类型

bool: 表示布尔值&#xff0c;只有两个取值&#xff1a;true 或 false&#xff0c;用于表示逻辑条件。int8: 表示 8 位的有符号整数&#xff0c;范围是 −128−128 到 127127。uint8: 表示 8 位的无符号整数&#xff0c;范围是 00 到 255255。int16: 表示 16 位的有符号整数&am…
阅读更多...
【SpringMVC】参数传递 重定向与转发 REST风格

【SpringMVC】参数传递 重定向与转发 REST风格

文章目录 参数传递重定向与转发REST风格 参数传递 ModelAndView&#xff1a;包含视图信息和模型数据信息 public ModelAndView index1(){// 返回页面ModelAndView modelAndView new ModelAndView("视图名");// 或// ModelAndView modelAndView new ModelAndView(…
阅读更多...
软件工程 概述

软件工程 概述

软件 不仅仅是一个程序代码。程序是一个可执行的代码&#xff0c;它提供了一些计算的目的。 软件被认为是集合可执行的程序代码&#xff0c;相关库和文档的软件。当满足一个特定的要求&#xff0c;就被称为软件产品。 工程 是所有有关开发的产品&#xff0c;使用良好定义的&…
阅读更多...
【数字化】华为企业数字化转型-认知篇

【数字化】华为企业数字化转型-认知篇

导读&#xff1a;企业数字化转型的必要性在于&#xff0c;它能够帮助企业适应数字化时代的需求&#xff0c;提升运营效率&#xff0c;创新业务模式&#xff0c;增强客户互动&#xff0c;从而在激烈的市场竞争中保持领先地位并实现可持续发展。通过学习华为企业数字化转型相关理…
阅读更多...
Android学习15--charger

Android学习15--charger

1 概述 最近正好在做关机充电这个&#xff0c;就详细看看吧。还是本着保密的原则&#xff0c;项目里的代码也不能直接用&#xff0c;这里就用的Github的。https://github.com/aosp-mirror 具体位置是&#xff1a;https://github.com/aosp-mirror/platform_system_core/tree/mai…
阅读更多...
Leetcode刷题(81~90)

Leetcode刷题(81~90)

算法是码农的基本功&#xff0c;也是各个大厂必考察的重点&#xff0c;让我们一起坚持写题吧。 遇事不决&#xff0c;可问春风&#xff0c;春风不语&#xff0c;即是本心。 我们在我们能力范围内&#xff0c;做好我们该做的事&#xff0c;然后相信一切都事最好的安排就可以啦…
阅读更多...
ARINC 标准全解析：航空电子领域多系列标准的核心内容、应用与重要意义

ARINC 标准全解析：航空电子领域多系列标准的核心内容、应用与重要意义

ARINC标准概述 ARINC标准是航空电子领域一系列重要的标准规范&#xff0c;由航空电子工程委员会&#xff08;AEEC&#xff09;编制&#xff0c;众多航空公司等参与支持。这些标准涵盖了从飞机设备安装、数据传输到航空电子设备功能等众多方面&#xff0c;确保航空电子系统的兼…
阅读更多...
【数据库】关系代数和SQL语句

【数据库】关系代数和SQL语句

一 对于教学数据库的三个基本表 学生S(S#,SNAME,AGE,SEX) 学习SC(S#,C#,GRADE) 课程(C#,CNAME,TEACHER) &#xff08;1&#xff09;试用关系代数表达式和SQL语句表示&#xff1a;检索WANG同学不学的课程号 select C# from C where C# not in(select C# from SCwhere S# in…
阅读更多...
学习记录：js算法（一百一十八）：连接所有点的最小费用

学习记录：js算法（一百一十八）：连接所有点的最小费用

文章目录 连接所有点的最小费用思路一 连接所有点的最小费用 给你一个points 数组&#xff0c;表示 2D 平面上的一些点&#xff0c;其中 points[i] [xi, yi] 。 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 &#xff1a;|xi - xj| |yi - yj| &#xff0c;其…
阅读更多...
Java项目实战II基于微信小程序的小区租拼车管理信息系统 （开发文档+数据库+源码）

Java项目实战II基于微信小程序的小区租拼车管理信息系统 （开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、核心代码 五、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 随着城市化进程的加速&#xff0c;小区居民对于出行方…
阅读更多...
数据结构与算法之美：单链表

数据结构与算法之美：单链表

Hello大家好&#xff01;很高兴我们又见面啦&#xff01;给生活添点passion&#xff0c;开始今天的编程之路&#xff01; 我的博客&#xff1a;<但凡. 我的专栏&#xff1a;《数据结构与算法之美》、《编程之路》、《题海拾贝》 欢迎点赞&#xff0c;关注&#xff01; 目录 …
阅读更多...
样品前处理工作站自动化操作

样品前处理工作站自动化操作

样品前处理工作站通过集成多种技术和自动化模块&#xff0c;实现了对样品的高效、精准处理。以下是实现自动化操作的关键步骤和原理&#xff1a; 1、集成多种技术&#xff1a;工作站通常集成了液体处理、固相萃取、离心、过滤等多种技术。这些技术的结合使得工作站能够完成从样…
阅读更多...
redis安装和使用教程【保姆级】

redis安装和使用教程【保姆级】

1.下载 通过网盘分享的文件&#xff1a;redis 链接: https://pan.baidu.com/s/1Tu1KZkf33YJFdul8s6SzqQ?pwd8888 提取码: 8888 2.启动 进入根目录&#xff0c;使用redis-server redis.windows.conf命令启行启动Redis服务&#xff0c; 如下图所示为启动成功&#xff0c;默认…
阅读更多...
RabbitMq 基础

RabbitMq 基础

文章目录 一、初识 MQ1.1 同步调用&#xff1a;1.2 异步调用&#xff1a; 二、RabbitMQ三、SpringAMQP3.1 依赖和配置文件3.2 消息发送和接收&#xff1a;3.2.1 消息发送&#xff1a;3.2.2 消息接收&#xff1a; 3.3 WorkQueues 模型&#xff1a;3.4 交换机类型&#xff1a;3.4…
阅读更多...
建筑行业数据分析如何做？

建筑行业数据分析如何做？

导读&#xff1a;在谈数字化转型之前&#xff0c;先来谈谈数据的价值。数字化转型的基础是数据&#xff0c;是数字化的基本的生产资料&#xff0c;数据的质量直接决定了数字化的能力、所能达到的深度和广度。目前做的数据可视化项目总感觉只是数据展现而已&#xff0c;而不达不…
阅读更多...
电脑投屏到电脑：Windows，macOS及Linux系统可以相互投屏！

电脑投屏到电脑：Windows，macOS及Linux系统可以相互投屏！

本篇其实是电脑远程投屏到另一台电脑的操作介绍。本篇文章的方法可用于Windows&#xff0c;macOS及Linux系统的相互投屏。 为了避免介绍过程中出现“这台电脑”投屏到“那台电脑”的混乱表述&#xff0c;假定当前屏幕投出端是Windows系统电脑&#xff0c;屏幕接收端是Linux系统…
阅读更多...
随时随地掌控数据：如何使用手机APP远程访问飞牛云NAS

随时随地掌控数据：如何使用手机APP远程访问飞牛云NAS

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
2024-12-04OpenCV视频处理基础

2024-12-04OpenCV视频处理基础

OpenCV视频处理基础 OpenCV的视频教学&#xff1a;https://www.bilibili.com/video/BV14P411D7MH 1-OpenCV视频捕获 在 OpenCV 中&#xff0c;cv2.VideoCapture() 是一个用于捕获视频流的类。它可以用来从摄像头捕获实时视频&#xff0c;或者从视频文件中读取帧。以下是如何使用…
阅读更多...
ubuntu安装navicat，并使用navicat连接mysql服务

ubuntu安装navicat，并使用navicat连接mysql服务

1.安装宝塔&#xff1a; 登录宝塔官网&#xff1a;https://www.bt.cn/new/download.html 使用对应命令安装宝塔&#xff0c;然后搭建mysql环境。 2.安装navicat 有需要教程的私我&#xff0c;我再更新整理出来 &#xff01;&#xff01;&#xff01; 有需要教程的私我&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023