【优选算法---归并排序衍生题目】剑指offer51---数组中的逆序对、计算右侧小于当前元素的个数、翻转对

embedded/2024/12/27 16:09:10/

一、剑指offer51---数组中的逆序对

题目链接:

LCR 170. 交易逆序对的总数 - 力扣(LeetCode)

题目介绍:

在数组中的两个数字,如果前面⼀个数字大于后面的数字,则这两个数字组成⼀个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例1:

  • 输入:[7,5,6,4]
  • 输出: 5

0 <= record.length <= 50000

思路:

        首先暴力解法就是先确定一个元素,然后遍历数组,找有多少个比他小的数,就是简单的两个循环,但是暴力解法是一定会超时的。

        接下来讲解一下更高效的方法。要求一个区间的所有的逆序对,我们可以将数组分为两部分,那结果就是 左部分的所有的逆序对 + 右部分的逆序对 + 一左一右选择的逆序对 ,会发现这个过程非常像归并排序的过程,所以们就往这个思路上想。

        如果单纯的按上面的步骤写,其实还是暴力的解法,但是如果我们在找到逆序逆序对后数组顺便排下序,这样找逆序对就会很快,排序并不会改变逆序对的个数,可以找一个例子验证一下。

最核心的问题,如何在合并两个有序数组的过程中,统计出逆序对的数量?

         合并两个有序序列时求逆序对的方法有两种:

  1. 在右边选一个数,看左边哪个比他大
  2. 在左边选一个数,看右边哪个比他小

方式1:在右边选一个数,看左边哪个比他小

  • 假设我们排的是升序:

假设此时如果 nums[begin1] <= nums[begin2] ,由于当前是升序,往后遍历也不会有元素比nums[begin1] 小,所以可以让begin1++,如果 nums[begin1] > nums[begin2] 的话,由于是升序的,所以从begin1 到 mid 之间的元素都大于nums[begin2] ,都符合逆序对,此时左部分可以与nums[begin2]组成逆序对的个数都统计出来了,就可以让begin2++,按照这个思路这个题目的事件复杂度和归并排序是一样的。

  • 那按照降序行不行呢?

我们来模拟一下,假设此时如果 nums[begin1] > nums[begin2] ,由于数组是降序那从begin到begin1之间的元素都大于nums[begin2] ,都可以与他构成逆序对,但是此时可以与nums[begin2]g构成逆序对的元素还没找完,因为不能确定begin1后面的元素是否还大于nums[begin2]。所以只能让begin1++,如果对应的这个元素仍然大于nums[begin2],我们就要继续计算begin 到 begin1 之间的元素,这样就会有重复的数据,所以方式一只能按升序处理

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& record) {return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int begin,int end){if(begin>=end) return 0;int mid=(begin+end)/2;int ret=0;ret+=MergeSort(record,begin,mid);ret+=MergeSort(record,mid+1,end);//处理一左一右int begin1=begin,end1=mid;int begin2=mid+1,end2=end;int j=0;while(begin1<=end1&&begin2<=end2){if(record[begin1]<=record[begin2]){//处理排序,顺便让begin1向后遍历tmp[j++]=record[begin1++];}else{ret+=(mid-begin1+1);tmp[j++]=record[begin2++];}}while(begin1<=end1)  tmp[j++]=record[begin1++];while(begin2<=end2)  tmp[j++]=record[begin2++];for(int i=begin;i<=end;i++)record[i]=tmp[i-begin];return ret;}
};

方式2:在左边选一个数,看右边哪个比他小

  • 假设我们排的是升序:

假设此时nums[begin1]>nums[bgein2],此时右边 mid+1 到 begin2 之间的数都小于nums[begin1],就可以统计结果, begin2++后,仍然有可能 nums[begin1]>nums[bgein2] ,此时统计的结果就存在重复,所以方式2只能采用降序的方式

  • 假设是降序

       

假设  nums[begin1]<=nums[bgein2] ,begin2就需要++,如果nums[begin1]>nums[bgein2] 的话,说明右边 begin2 到end之间的元素都小于nums[begin1],此时右边可以与nums[begin1]构成逆序对的数都统计出来了,begin1就可以++

 

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& record) {return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int begin,int end){if(begin>=end) return 0;int mid=(begin+end)/2;int ret=0;ret+=MergeSort(record,begin,mid);ret+=MergeSort(record,mid+1,end);//处理一左一右int begin1=begin,end1=mid;int begin2=mid+1,end2=end;int j=0;while(begin1<=end1&&begin2<=end2){if(record[begin1]<=record[begin2]){tmp[j++]=record[begin2++];}else{ret+=(end-begin2+1);tmp[j++]=record[begin1++];}}while(begin1<=end1)  tmp[j++]=record[begin1++];while(begin2<=end2)  tmp[j++]=record[begin2++];for(int i=begin;i<=end;i++)record[i]=tmp[i-begin];return ret;}
};

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

题目链接:

315. 计算右侧小于当前元素的个数 - 力扣(LeetCode)

题目介绍:

给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
思路:

这个题目的思路完全和上一个题目一样,不同的地方是这个题要我们返回一个数组,数组的元素代表nums对应那个元素的逆序对个数,我们上面的思路实在归并排序的过程中计算出逆序对的,但是由于要排序,数组元素的对应位置也会改变,所以我们需要解决这个问题即可。

通过元素的值构建哈希表这个方案是不能用的,因为数组可能会有重复的元素,但是我们还是要利用哈希的原理,我们可以创建一个数组index,让这个数组映射nums每个元素的下标,在对nums排序时,连带index数组一起排序,这样映射关系就建立好了。

所以我们一共需要创建两个辅助数组,tmpNums、tmpIndex,一个用来辅助Nums排序,一个用来辅助index数组排序

class Solution {
public:int tmpNums[500010];int tmpIndex[500010];vector<int> ret;vector<int> index;vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);// 构建映射for (int i = 0; i < n; i++) {index[i] = i;}MergeSort(nums, 0, n - 1);return ret;}void MergeSort(vector<int>& nums,int begin,int end){if(begin>=end)return;int mid=(begin+end)/2;MergeSort(nums,begin,mid);MergeSort(nums,mid+1,end);int begin1=begin,end1=mid;int begin2=mid+1,end2=end;int j=0;while(begin1<=end1&&begin2<=end2){if(nums[begin1]<=nums[begin2]){tmpNums[j]=nums[begin2];tmpIndex[j++]=index[begin2++];}else{ret[index[begin1]]+=(end2-begin2+1);tmpNums[j]=nums[begin1];tmpIndex[j++]=index[begin1++];}}while(begin1<=end1){tmpNums[j]=nums[begin1];tmpIndex[j++]=index[begin1++];}while(begin2<=end2){tmpNums[j]=nums[begin2];tmpIndex[j++]=index[begin2++];}for (int i = begin; i <= end; i++) {nums[i] = tmpNums[i - begin];index[i] = tmpIndex[i - begin];}}
};

 三、翻转对

题目链接:

493. 翻转对 - 力扣(LeetCode)

题目介绍:

给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对

你需要返回给定数组中的重要翻转对的数量。

  • 给定数组的长度不会超过50000
  • 输入数组中的所有数字都在32位整数的表示范围内。
思路:

这个题目的思路与逆序对那个题目几乎一样,不同的是逆序对那个题找的是nums[i]>nums[j],与归并排序的判断一致,所以就一边合并一边计算了,但是这个题的判断是大于2倍,与归并排序的判断条件并不符合,如果硬要边和并边计算从理论上说是可以的,但是这样会增加程序的复杂度,所以我们需要在归并前,利用两边是有序的特性,计算出翻转对的个数。

假设我们是降序的,如果nuns[begin1] <= nums[begin2] *2的话,就让cur2++,如果

nuns[begin1] > nums[begin2]*2 的话,由于是降序,begin2到end之间的元素也是符合要求的,此时让begin1++,继续判断,这样指针没有回退,求翻转对的时间复杂度就是O(N)

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& nums) {return MergeSort(nums,0,nums.size()-1);}int MergeSort(vector<int>& nums,int begin,int end){if(begin>=end) return 0;int mid=(begin+end)/2;int ret=0;ret+=MergeSort(nums,begin,mid);ret+=MergeSort(nums,mid+1,end);//处理翻转对int begin1=begin,end1=mid;int begin2=mid+1,end2=end;while(begin1<=end1){while(begin2<=end2&&nums[begin2]>=nums[begin1]/2.0)begin2++;if(begin2>end2)break;ret+=end-begin2+1;begin1++;}//处理一左一右begin1=begin,end1=mid;begin2=mid+1,end2=end;int j=0;while(begin1<=end1&&begin2<=end2){if(nums[begin1]<=nums[begin2]){tmp[j++]=nums[begin2++];}else{tmp[j++]=nums[begin1++];}}while(begin1<=end1)  tmp[j++]=nums[begin1++];while(begin2<=end2)  tmp[j++]=nums[begin2++];for(int i=begin;i<=end;i++)nums[i]=tmp[i-begin];return ret;}
};


http://www.ppmy.cn/embedded/149206.html

相关文章

Linux复习4——shell与文本处理

认识vim编辑器 #基本语法格式&#xff1a; vim 文件名 •如果文件存在&#xff0c;进入编辑状态对其进行编辑 •如果文件不存在&#xff0c;创建文件并进入编辑状态 例&#xff1a; [rootlocalhosttest]# vim practice.txt #Vim 编辑器三种模式&#xff1a; 命令模式&a…

stm32能跑人工智能么

STM32确实能够运行人工智能算法&#xff0c;这得益于其强大的计算能力和丰富的外设接口&#xff0c;为运行小型人工智能算法提供了基础。以下是对STM32运行人工智能能力的详细分析&#xff1a; 一、硬件基础 STM32作为一款广泛应用于工业控制、智能家居等领域的微控制器&…

OCR实践-Table-Transformer

前言 书接上文 OCR实践—PaddleOCR Table-Transformer 与 PubTables-1M table-transformer&#xff0c;来自微软&#xff0c;基于Detr&#xff0c;在PubTables1M 数据集上进行训练&#xff0c;模型是在提出数据集同时的工作&#xff0c; paper PubTables-1M: Towards comp…

全国硕士研究生入学考试(考研)常识详解之分数构成:初试成绩、复试成绩及复录比

考研分数构成全解析&#xff1a;初试成绩、复试成绩及复录比详解 全国硕士研究生入学考试&#xff08;考研&#xff09;的成绩评定由初试和复试两个阶段组成&#xff0c;最终成绩决定考生的录取结果。在此过程中&#xff0c;复试比例及复录比是考生需要重点关注的因素。以下将…

美畅物联丨如何在视频汇聚平台上添加RTMP主动推流设备?

我们前面经常提起视频汇聚平台运用流媒体传输协议接入各类视频源设备&#xff0c;对分散的各种视频资源予以统一汇聚、整合并集中管理。这类平台不但支持多种接入形式&#xff0c;涵盖标准协议&#xff08;像GB28181、RTSP/Onvif、RTMP等&#xff09;以及厂家私有协议和SDK接入…

网络层协议--ip协议

目录 引言 IP协议 协议头格式 16位标识与3位标志与13位片偏移讲解 网段划分(重要) DHCP技术 CIDR技术 特殊的IP地址 广播主机 IP地址的数量限制 私有IP地址和公网IP地址 路由&#xff1a;在复杂的网络结构中, 找出一条通往终点的路线 简单认识路由器 路由表生成算…

golang标准库SSH操作示例

文章目录 前言一、了解SSH二、重要知识点1.安装ssh库2.ssh库重要知识牢记 三、模拟连接远程服务器并执行命令四、SSH与os/exec标准库下执行命令的几种方式对比五、SSH库下三种执行命令方式演示5.1. session.CombinedOutput()示例5.2. session.Run()示例5.3. session.Start()、s…

【Rust自学】7.2. 路径(Path)Pt.1:相对路径、绝对路径与pub关键字

喜欢的话别忘了点赞、收藏加关注哦&#xff08;加关注即可阅读全文&#xff09;&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 7.2.1. 路径的简介 在Rust里&#xff0c;如果想要找到模块里的某个东西&#xff0c;就必须知…