[Algorithm][分治 - 归并排序][排序数组][交易逆序对的总数][计算右侧小于当前元素的个数][翻转对]详细讲解

目录

  • 0.原理讲解
  • 1.排序数组
    • 1.题目链接
    • 2.代码实现
  • 2.交易逆序对的总数
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 3.计算右侧小于当前元素的个数
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 4.翻转对
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现

0.原理讲解

  • 归并排序的流程充分的体现了**「分⽽治之」**的思想，⼤体过程分为两步
    • 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为1 ，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」
    • 治：将两个较短的**「有序数组合并成⼀个⻓的有序数组」**，⼀直合并到最初的⻓度
    • 本质类似二叉树的后序遍历
      请添加图片描述

1.排序数组

1.题目链接

  • 排序数组

2.代码实现

  • 递归时，创建vector开销挺大的 -> 辅助数组放全局
class Solution 
{
    vector<int> assist; // 归并时的辅助数组
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        assist.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return;
        }

        // 1.选择中间点划分区间
        int mid = left + (right - left) / 2;

        // 2.排序左右区间
        // [left, mid] [mid + 1, right]
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);

        // 3.合并两个有序数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            assist[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        // 4.处理没有遍历完的数组
        while(cur1 <= mid)
        {
            assist[i++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            assist[i++] = nums[cur2++];
        }

        // 5.还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assist[i - left];
        }
    }
};

2.交易逆序对的总数

1.题目链接

  • 交易逆序对的总数

2.算法原理详解

  • 解法：利用归并排序的分治过程

    • 左半部分 -> 左派序 -> 右半部分 -> 右排序 -> 一左一右 -> 排序
    • 在归并排序的合并过程中统计出逆序对的数量

  • 注意：默认都是升序，如果掌握升序，结合问题，降序的归并过程也是可以解决问题的

  • 为什么可以利用归并排序？

    • 如果将数组从中间划分成两个部分，那么可以将逆序对产⽣的⽅式划分成三组
      • 全部从左数组中选择
      • 全部从右数组中选择
      • ⼀个选左数组另⼀个选右数组
    • 根据排列组合的分类相加原理，三种情况下产⽣的逆序对的总和，正好等于总的逆序对数量
    • ⽽这个思路正好匹配归并排序的过程
      • 先排序左数组
      • 再排序右数组
      • 左右数组合二为一
    • 因此，可以利⽤归并排序的过程
      • 先求出左半数组中逆序对的数量
      • 再求出右半数组中逆序对的数量
      • 最后求出⼀个选择左边，另⼀个选择右边情况下逆序对的数量，三者相加即可

  • 为什么要这么做？

    • 在归并排序合并的过程中，得到的是两个有序的数组
    • 可以利⽤数组的有序性，快速统计出逆序对的数量，⽽不是将所有情况都枚举出来

  • 如何在合并两个有序数组的过程中，统计出逆序对的数量？

    • 合并两个有序序列时求逆序对的⽅法有两种
      • 快速统计出某个数前⾯有多少个数⽐它⼤ <- 升序
        • 降序无法实现
      • 快速统计出某个数后⾯有多少个数⽐它⼩ <- 降序
        • 升序无法实现

  • 法一：快速统计出某个数前⾯有多少个数⽐它⼤

    • 在合并有序数组的时候，遇到左数组当前元素 > 右数组当前元素时，可以通过计算左数组中剩余元素的⻓度，就可快速求出右数组当前元素前⾯有多少个数⽐它⼤
      请添加图片描述

  • 法二：快速统计出某个数后⾯有多少个数⽐它⼩

    • 在合并有序数组的时候，遇到左数组当前元素 <= 右数组当前元素时，可以通过计算右数组已经遍历过的元素的⻓度，快速求出左数组当前元素后⾯有多少个数⽐它⼤
      请添加图片描述

3.代码实现

// v1.0 升序
class Solution 
{
    vector<int> assist;
public:
    int ReversePairs(vector<int>& nums) 
    {
        assist.resize(nums.size());
        return MergeSort(nums, 0, nums.size() - 1);
    }

    int MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        int ret = 0;
        // 选择中点，划分数组
        int mid = left + (right - left) / 2;

        // 左边的个数 + 排序 + 右边的个数 + 排序
        // [left, mid] [mid + 1, right]
        ret += MergeSort(nums, left, mid);
        ret += MergeSort(nums, mid + 1, right);

        // 一左一右的个数 + 排序
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                assist[i++] = nums[cur1++];
            }
            else
            {
                ret += mid - cur1 + 1;
                assist[i++] = nums[cur2++];
            }
        }

        // 处理未遍历完的数组
        while(cur1 <= mid)
        {
            assist[i++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            assist[i++] = nums[cur2++];
        }

        // 还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assist[i - left];
        }

        return ret;
    }
};
----------------------------------------------------------------------------
// v2.0 降序
class Solution 
{
    vector<int> assist;
public:
    int reversePairs(vector<int>& nums) 
    {
        assist.resize(nums.size());
        return MergeSort(nums, 0, nums.size() - 1);
    }

    int MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        int ret = 0;
        // 选择中点，划分数组
        int mid = left + (right - left) / 2;

        // 左边的个数 + 排序 + 右边的个数 + 排序
        // [left, mid] [mid + 1, right]
        ret += MergeSort(nums, left, mid);
        ret += MergeSort(nums, mid + 1, right);

        // 一左一右的个数 + 排序
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                assist[i++] = nums[cur2++];
            }
            else
            {
                ret += right - cur2 + 1;
                assist[i++] = nums[cur1++];
            }
        }

        // 处理未遍历完的数组
        while(cur1 <= mid)
        {
            assist[i++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            assist[i++] = nums[cur2++];
        }

        // 还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assist[i - left];
        }

        return ret;
    }
};

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

1.题目链接

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

2.算法原理详解

  • 思路：解法与「求数组中的逆序对」的解法类似，但是本题要返回⼀个数组，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩

  • 在归并排序的过程中，元素的下标是会跟着变化的

    • 因此需要⼀个辅助数组，来将数组元素和对应的下标绑定在⼀起归并
    • 也就是在归并元素的时候，顺势将下标也转移到对应的位置上
      请添加图片描述

  • 创建两个全局的数组

    • vector<int> ret -> 记录结果
    • vector<int> index -> 记录下标
      请添加图片描述

3.代码实现

class Solution 
{
    vector<int> ret;
    vector<int> index;
    vector<int> assistNums;
    vector<int> assistIndex;
public:
    vector<int> CountSmaller(vector<int>& nums) 
    {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        assistNums.resize(n);
        assistIndex.resize(n);
        
        // 初始化index
        for(int i = 0; i < n; i++)
        {
            index[i] = i;
        }
        
        MergeSort(nums, 0, n - 1);
        
        return ret;
    }
    
    void MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return;
        }
        
        // 中间点，划分数组
        int mid = left + (right - left) / 2;
        // [left, mid] [mid + 1, right]
        
        // 先处理左右子数组
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);
        
        // 处理一左一右 + 排序(降序)
        // 元素和下标同步迁移
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                assistNums[i] = nums[cur2];
                assistIndex[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1; // 统计 -> 重点
                assistNums[i] = nums[cur1];
                assistIndex[i++] = index[cur1++];
            }
        }
        
        // 处理未遍历完数组
        while(cur1 <= mid)
        {
            assistNums[i] = nums[cur1];
            assistIndex[i++] = index[cur1++];
        }
        
        while(cur2 <= right)
        {
            assistNums[i] = nums[cur2];
            assistIndex[i++] = index[cur2++];
        }
        
        // 还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assistNums[i - left];
            index[i] = assistIndex[i - left];
        }
    }
};

4.翻转对

1.题目链接

  • 翻转对

2.算法原理详解

  • 思路解析：

    • ⼤思路与求逆序对的思路⼀样，利⽤归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：
      • 左半区间翻转对的数量，右半区间翻转对的数量，⼀左⼀右选择时翻转对的数量
    • 重点就是在合并区间过程中，如何计算出翻转对的数量
      • 与上个问题不同的是，上⼀道题可以⼀边合并⼀遍计算，但是这道题要求的是左边元素⼤于右边元素的两倍，如果直接合并的话，是⽆法快速计算出翻转对的数量的
        请添加图片描述

  • 计算翻转对：利用单调性，使用同向双指针

    • 法一：计算当前元素后面，有多少元素的两倍比我小 -> 降序
    • 法二：计算当前元素之前，有多少元素的一半比我大 -> 升序

3.代码实现

// v1.0 降序
class Solution 
{
    vector<int> assist;
public:
    int reversePairs(vector<int>& nums) 
    {
        assist.resize(nums.size());
        return MergeSort(nums, 0, nums.size() - 1);
    }

    int MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        int ret = 0;
        // 中间点，划分两区间
        int mid = left + (right - left) / 2;
        // [left, mid] [mid + 1, right]
    
        // 先计算左右子区间翻转对
        ret += MergeSort(nums, left, mid);
        ret += MergeSort(nums, mid + 1, right);

        // 计算一左一右翻转对的数量
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid) // 降序 固定cur1
        {
	        // * -> / 防溢出
	        // / 2.0确保能除尽
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
            {
                cur2++;
            }
            
			// 优化
            if(cur2 > right)
            {
                break;
            }

            ret += right - cur2 + 1;
            cur1++;
        }

        // 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            assist[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }

        // 处理未遍历完数组
        while(cur1 <= mid)
        {
            assist[i++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            assist[i++] = nums[cur2++];
        }

        // 还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assist[i - left];
        }

        return ret;
    }
};
-------------------------------------------------------------------------
// v2.0 升序
class Solution 
{
    vector<int> assist;
public:
    int reversePairs(vector<int>& nums) 
    {
        assist.resize(nums.size());
        return MergeSort(nums, 0, nums.size() - 1);
    }

    int MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        int ret = 0;
        // 中间点，划分两区间
        int mid = left + (right - left) / 2;
        // [left, mid] [mid + 1, right]
    
        // 先计算左右子区间翻转对
        ret += MergeSort(nums, left, mid);
        ret += MergeSort(nums, mid + 1, right);

        // 计算一左一右翻转对的数量
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur2 <= right) // 升序  固定cur2
        {
            while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0)
            {
                cur1++;
            }

			// 优化
            if(cur1 > mid)
            {
                break;
            }

            ret += mid - cur1 + 1;
            cur2++;
        }

        // 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            assist[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        // 处理未遍历完数组
        while(cur1 <= mid)
        {
            assist[i++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            assist[i++] = nums[cur2++];
        }

        // 还原
        for(int i = left; i <= right; i++)
        {
            nums[i] = assist[i - left];
        }

        return ret;
    }
};

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

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

相关文章

使用CSgetshell到3389端口远程桌面

使用CSgetshell到3389端口远程桌面

中间使用了这个Akagi64.exe提权&#xff0c;网上可以找到&#xff0c;高版本的cs网上也可以找到。
阅读更多...
Linux系统编程---线程池并发服务器

Linux系统编程---线程池并发服务器

模型原理分析&#xff1a; 线程池的关键优势在于它减少了每次任务执行时创建和销毁线程的开销 线程池的组成主要分为 3 个部分&#xff0c;这三部分配合工作就可以得到一个完整的线程池&#xff1a; 1. 任务队列&#xff0c;存储需要处理的任务&#xff0c;由工作的线程来处理…
阅读更多...
Linux网络服务-DHCP

Linux网络服务-DHCP

一、DHCP工作原理 DHCP&#xff08;Dynamic Host Configuration Protocol&#xff0c;动态主机配置协议&#xff09;&#xff1a;用于自动获取IP地址 1.客户端会发送一个广播DHCP Discover报文去寻找DHCP服务器 2.客户端只会接收第一个回复的DHCP服务器的报文 3.服务器会发…
阅读更多...
MATLAB非均匀网格梯度计算

MATLAB非均匀网格梯度计算

在matlab中&#xff0c;gradient函数可以很方便的对均匀网格进行梯度计算&#xff0c;但是对于非均匀网格&#xff0c;但是gradient却无法求解非均匀网格的梯度&#xff0c;这一点我之前犯过错误。我之前以为在gradient函数中指定x&#xff0c;y等坐标&#xff0c;其求解的就是…
阅读更多...
Python异步Redis客户端与通用缓存装饰器

Python异步Redis客户端与通用缓存装饰器

前言 这里我将通过 redis-py 简易封装一个异步的Redis客户端&#xff0c;然后主要讲解设计一个支持各种缓存代理&#xff08;本地内存、Redis等&#xff09;的缓存装饰器&#xff0c;用于在减少一些不必要的计算、存储层的查询、网络IO等。 具体代码都封装在 HuiDBK/py-tools: …
阅读更多...
Ubuntu TeamViewer安装与使用

Ubuntu TeamViewer安装与使用

TeamViewer是一款跨平台的专有应用程序&#xff0c;允许用户通过互联网连接从全球任何地方远程连接到工作站、传输文件以及召开在线会议。它适用于多种设备&#xff0c;例如个人电脑、智能手机和平板电脑。 TeamViewer可以派上用场&#xff0c;尤其是在排除交通不便或偏远地区…
阅读更多...
Open SUSE 安装MySQL

Open SUSE 安装MySQL

前言 看了一圈网上关于SUSE的教程实在是太少了&#xff0c;毕竟太小众了。这两天在安装MySQL的时候老是出问题&#xff0c;踩了一晚上的坑&#xff0c;发现其实很简单&#xff0c;网上看了方法大概有这几种 通过Yast software management安装&#xff0c;但是我尝试了&#x…
阅读更多...
Linux下的基本指令（1）

Linux下的基本指令（1）

嗨喽大家好呀&#xff01;今天阿鑫给大家带来Linux下的基本指令&#xff08;1&#xff09;&#xff0c;下面让我们一起进入Linux的学习吧&#xff01; Linux下的基本指令 ls 指令pwd命令cd 指令touch指令mkdir指令(重要)rmdir指令 && rm 指令(重要)man指令(重要)cp指…
阅读更多...
海外三大AI图片生成器对比（Stable Diffusion、Midjourney、DALL·E 3）

海外三大AI图片生成器对比（Stable Diffusion、Midjourney、DALL·E 3）

Stable Diffusion DreamStudio 是Stable Diffusion 的官方网页&#xff0c;价格便宜&#xff0c;对图片的操作性强&#xff0c;但同时编辑页面不太直观&#xff0c;对使用者的要求较高。 与 DALLE 和 Midjourney 不同&#xff0c;Stable Diffusion 是开源的。这也意味着&…
阅读更多...
[图解]领域驱动设计伪创新-为什么互联网是重灾区-02

[图解]领域驱动设计伪创新-为什么互联网是重灾区-02

0 00:00:00,000 --> 00:00:04,737 我们并没有说&#xff0c;微信或者是美团用了领域驱动设计 1 00:00:04,737 --> 00:00:06,632 没有做这个暗示 2 00:00:06,632 --> 00:00:08,290 我只是说什么 3 00:00:09,350 --> 00:00:12,700 针对用户量很大的系统 4 00:00:…
阅读更多...
CANoe如何实现TLS协议

CANoe如何实现TLS协议

TLS&#xff0c;Transport Layer Security&#xff0c;传输层安全协议。是在传输层和应用层之间&#xff0c;为了保证应用层数据能够安全可靠地通过传输层传输且不会泄露的安全防护。 TLS安全协议的实现逻辑&#xff0c;在作者本人看来&#xff0c;大致分为三个部分&#xff1…
阅读更多...
minio主从同步和双机热备

minio主从同步和双机热备

文章目录 1. 安装2. 测试3. 双机热备 环境说明 服务器IPminio-slb10.10.xxx.251minio-01/02/03/0410.10.xxx.25/206/207/208minio-backup10.10.xxx.204 1. 安装 下载地址&#xff1a; http://dl.minio.org.cn/client/mc/release/linux-amd64/mc 安装 只有一个二进制文件&…
阅读更多...
Spring Security OAuth2 统一登录

Spring Security OAuth2 统一登录

介绍 Spring Security OAuth2 是一个在 Spring Security 框架基础上构建的 OAuth2 授权服务器和资源服务器的扩展库。它提供了一套功能强大的工具和组件&#xff0c;用于实现 OAuth2 协议中的授权流程、令牌管理和访问控制。 Git地址&#xff1a;yunfeng-boot3-sercurity: Sp…
阅读更多...
贴片OB2500POPA OB2500POP SOP-8 电源开关控制器IC芯片

贴片OB2500POPA OB2500POP SOP-8 电源开关控制器IC芯片

OB2500POPA电源管理芯片被广泛应用于各种低功耗AC-DC充电器和适配器中。以下是该芯片的一些典型应用案例&#xff1a; 手机充电器&#xff1a;OB2500POPA可以用于设计高效、小巧的手机充电器&#xff0c;提供稳定的输出电压和电流。 USB充电器&#xff1a;在USB充电器中&…
阅读更多...
第5篇：创建Nios II工程之Hello_World＜四＞

第5篇：创建Nios II工程之Hello_World＜四＞

Q&#xff1a;最后我们在DE2-115开发板上演示运行Hello_World程序。 A&#xff1a;先烧录编译Quartus硬件工程时生成的.sof文件&#xff0c;在FPGA上成功配置Nios II系统&#xff1b;然后在Nios II Eclipse窗口右键点击工程名hello_world&#xff0c;选择Run As-->Nios II …
阅读更多...
Node.js 版本升级方法

Node.js 版本升级方法

在构建vue项目时&#xff0c;依赖npm&#xff08;Node Package Manager&#xff09;工具&#xff0c;类似于Java项目需要maven管理。而npm是node.js的管理工具&#xff0c;npm依赖node.js环境才能执行。 有时候使用voscode或者其他工具安装vue项目依赖&#xff0c;显示一直处于…
阅读更多...
Apollo共创生态：共筑未来智能出行新篇章

Apollo共创生态：共筑未来智能出行新篇章

目录 引言Apollo七周年大会回顾心路历程企业生态计划 个人心得与启发技术革新的引领者展望 结语 引言 在科技飞速发展的今天&#xff0c;智能出行已经成为全球关注的焦点。Apollo开放平台&#xff0c;作为智能出行领域的先行者&#xff0c;已经走过了七个春秋。七年磨一剑&…
阅读更多...
vue3+antv+ts实现勾选同意协议复选框之后才能继续注册登录

vue3+antv+ts实现勾选同意协议复选框之后才能继续注册登录

效果如下&#xff1a; 勾选复选框之前 勾选复选框之后 这里偷懒了&#xff0c;没有把登录和注册按钮分开控制&#xff0c;自己实操的时候可以去细化一下功能 代码如下&#xff1a; <script setup lang"ts"> import { ref, defineProps, reactive } from &qu…
阅读更多...
【Spring Boot 源码学习】SpringApplication 的 run 方法监听器

【Spring Boot 源码学习】SpringApplication 的 run 方法监听器

《Spring Boot 源码学习系列》 SpringApplication 的 run 方法监听器 一、引言二、主要内容2.1 SpringApplicationRunListeners2.2 SpringApplicationRunListener2.3 实现类 EventPublishingRunListener2.3.1 成员变量和构造方法2.3.2 成员方法2.3.2.1 不同阶段的事件处理2.3.2…
阅读更多...
分享一些常用的内外网文件传输工具

分享一些常用的内外网文件传输工具

内外网隔离后的文件传输是网络安全领域中一个常见而又重要的问题。随着信息技术的快速发展&#xff0c;网络安全问题日益凸显&#xff0c;内外网隔离成为了许多企业和组织保护内部信息安全的重要手段。然而&#xff0c;内外网隔离后如何有效地进行文件传输&#xff0c;成为了摆…
阅读更多...
最新文章

Copyright @ 2022~2023