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

一、剑指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.rhkb.cn/news/494022.html

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

相关文章

C++算法第十二天

本篇文章&#xff0c;我们继续学习动态规划 第一题 题目链接 面试题 17.16. 按摩师 - 力扣&#xff08;LeetCode&#xff09; 题目解析 代码原理 代码编写 细节问题处理 这里的细节问题就是当n 0时的这种情况 完整源代码 class Solution { public: int massage(vector&…

java全栈day20--Web后端实战(Mybatis基础2)

一、Mybatis基础 1.1辅助配置 配置 SQL 提示。 默认在 mybatis 中编写 SQL 语句是不识别的。可以做如下配置&#xff1a; 现在就有sql提示了 新的问题 产生原因&#xff1a; Idea 和数据库没有建立连接&#xff0c;不识别表信息 解决方式&#xff1a;在 Idea 中配置 MySQL 数…

2023年厦门市第30届小学生C++信息学竞赛复赛上机操作题(三、2023C. 太空旅行(travel))

#include <bits/stdc.h>using namespace std;struct Ship {int u; // 从地球到火星的时间int v; // 从火星到天王星的时间 };// 自定义比较函数 bool cmp(const Ship &a, const Ship &b) {return a.u max(a.v, b.u) b.v < b.u max(b.v, a.u) a.v; }int ma…

使用qemu搭建armv7嵌入式开发环境

目录 目录 1 概述 2 环境准备 2.1 vexpress系列开发板介绍 2.2 安装工具 2.2.1 安装交叉工具链 2.2.2 安装qemu 2.2.3 安装其他工具 3 启动uboot 3.1 uboot下载与编译 3.1.1 下载 3.1.2 编译 3.2 使用qemu启动uboot 4 启动kernel 4.1 下载和编译kernel 4.1.1 下…

CSDN外链失效3:

参考我之前的博客&#xff1a; 外链失效博客1&#xff1a;随想笔记1&#xff1a;CSDN写博客经常崩溃&#xff0c;遇到外链图片转存失败怎么办_csdn外链图片转存失败-CSDN博客 外链失效博客2&#xff1a;网络随想2&#xff1a;转语雀_md格式转语雀lake格式-CSDN博客 markdown…

《LangChain大模型应用开发》书籍分享

前言 ChatGPT和OpenAI开发的GPT模型不仅改变了我们的写作和研究方式&#xff0c;还改变了我们处理信息的方式。《LangChain大模型应用开发》讨论了聊天模式下的LLM的运作、能力和局限性&#xff0c;包括ChatGPT和Gemini。书中通过一系列实际例子演示了如何使用LangChain框架构…

Jenkins持续集成部署——jenkins安装

前言 Jenkins 是一个开源的自动化服务器&#xff0c;主要用于持续集成&#xff08;CI&#xff09;和持续交付&#xff08;CD&#xff09;。它为软件开发团队提供了一个易于使用的平台来自动化构建、测试和部署应用程序的过程。 Jenkins 主要功能 1. 持续集成 (CI) 自动构建…

飞牛 fnos 使用docker部署 bili-sync:打造自动化 B 站资源下载器,与主流媒体服务器无缝衔接

Bili-Sync介绍及相关部署操作 一、Bili-Sync概述 Bili-Sync是哔哩哔哩内容同步助手&#xff0c;它能借助用户提供的登录信息&#xff0c;定期对用户的视频合集以及个人收藏进行遍历&#xff0c;找出还没在本地保存的新内容&#xff0c;然后自动下载到本地存储&#xff0c;以此…

Idean 处理一个项目引用另外一个项目jar 但jar版本低的问题

当在idea中一个module A引用另外一个项目B的jar&#xff0c;但是从私服仓库中拉下的jar版本比较低导致编译不通过时&#xff0c;可以把项目B拉下来&#xff0c;重新编译打包jar跟新到本地的仓库 选中右边菜单的Maven 选中对应的项目B-》Lifecycle->双击 install也可以按住c…

【day11】面向对象编程进阶(继承)

概述 本文深入探讨面向对象编程的核心概念&#xff0c;包括继承、方法重写、this和super关键字的使用&#xff0c;以及抽象类和方法的定义与实现。通过本文的学习&#xff0c;你将能够&#xff1a; 理解继承的优势。掌握继承的使用方法。了解继承后成员变量和成员方法的访问特…

高效准确的PDF解析工具,赋能企业非结构化数据治理

目录 准确性高&#xff1a;还原复杂版面元素 使用便捷&#xff1a;灵活适配场景 贴心服务&#xff1a;快速响应机制 在数据为王的时代浪潮中&#xff0c;企业数据治理已成为组织优化运营、提高竞争力的关键。随着数字化进程的加速&#xff0c;企业所积累的数据量呈爆炸式增长…

Unity全局雾效

1、全局雾效是什么 全局雾效&#xff08;Global Fog&#xff09;是一种视觉效果&#xff0c;用于在3D场景中模拟大气中的雾气对远处物体的遮挡 它通过在场景中加入雾的效果&#xff0c;使得距离摄像机较远的物体看起来逐渐被雾气覆盖&#xff0c;从而创造出一种朦胧、模糊的视…

解决Apache/2.4.39 (Win64) PHP/7.2.18 Server at localhost Port 80问题

配置一下apache里面的配置文件&#xff1a;httpd.conf 和 httpd.vhosts.conf httpd.conf httpd-vhosts.conf 重启服务 展示&#xff1a; 浏览器中中文乱码问题&#xff1a;

【Spring事务】深入浅出Spring事务从原理到源码

什么是事务 保证业务操作完整性的一种数据库机制 &#xff08;driver 驱动&#xff09;事务特定 ACID A 原子性 &#xff08;多次操作 要不一起成功 要不一起失败 &#xff08;部分失败 savepoint&#xff09;&#xff09; C 一致性 &#xff08;事务开始时数据状态&#xff0c…

MFC/C++学习系列之简单记录13

MFC/C学习系列之简单记录13 前言memsetList Control代码注意 总结 前言 今天记录一下memset和List control 的使用吧&#xff01; memset memset通常在初始化变量或清空内存区域的时候使用&#xff0c;可以对变量设定特定的值。 使用&#xff1a; 头文件&#xff1a; C&#…

C# cad启动自动加载启动插件、类库编译 多个dll合并为一个

可以通过引用costura.fody的包&#xff0c;编译后直接变为一个dll 自动加载写入注册表、激活码功能: 【CAD二次开发教程-实例18-启动加载与自动运行-哔哩哔哩】 https://b23.tv/lKnki3f https://gitee.com/zhuhao1912/cad-atuo-register-and-active

Android Studio AI助手---Gemini

从金丝雀频道下载最新版 Android Studio&#xff0c;以利用所有这些新功能&#xff0c;并继续阅读以了解新增内容。 Gemini 现在可以编写、重构和记录 Android 代码 Gemini 不仅仅是提供指导。它可以编辑您的代码&#xff0c;帮助您快速从原型转向实现&#xff0c;实现常见的…

固定电话采用的是模拟信号还是数字信号?如果通话两端采用不同的信号会发生什么?

固定电话信号大揭秘&#xff1a;模拟与数字信号的纠缠 模拟信号 VS 数字信号&#xff1a;谁是电话界的“老江湖”&#xff1f; 固定电话采用的是模拟信号还是数字信号&#xff1f; 这其实取决于接入方式&#xff1a; 铜线接入&#xff1a;传统方式&#xff0c;使用模拟电信号…

<项目代码>YOLO Visdrone航拍目标识别<目标检测>

项目代码下载链接 &#xff1c;项目代码&#xff1e;YOLO Visdrone航拍目标识别&#xff1c;目标检测&#xff1e;https://download.csdn.net/download/qq_53332949/90163918YOLOv8是一种单阶段&#xff08;one-stage&#xff09;检测算法&#xff0c;它将目标检测问题转化为一…

druid与pgsql结合踩坑记

最近项目里面突然出现一个怪问题&#xff0c;数据库是pgsql&#xff0c;jdbc连接池是alibaba开源的druid&#xff0c;idea里面直接启动没问题&#xff0c;打完包放在centos上和windows上cmd窗口都能直接用java -jar命令启动&#xff0c;但是放到国产信创系统上就是报错&#xf…