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

算法:分治思想处理归并递归问题

文章目录

  • 算法原理
  • 实现思路
  • 典型例题
    • 排序数组
    • 数组中的逆序对
    • 计算右侧小于当前元素的个数
  • 总结

算法原理

利用归并思想进行分治也是很重要的一种思路,在解决逆序对的问题上有很大的需求空间

于是首先归并排序是首先的,归并排序要能写出来:

class Solution 
{vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){if(left>=right){return;}// 数组划分 [left,mid][mid+1,right]int mid=(left+right)/2;// 分块排序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]){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];}}
};

以上为归并排序基本算法原理,基于这个原理可以解决逆序对问题,逆序对问题通常问法是,给定某一个数据,在整个数组中找比这个数大或者比这个数小的数,统计这样的元素有多少个,进而返回到数组或者直接输出

那么在找寻这个过程中,这类问题的基本思路就是:左边找,右边找,左右找

在找寻的过程中需要注意的是升序和逆序问题,后续的题目中会有涉及到的地方,在这里不过总结

实现思路

大体的实现思路如上,总结下来就是划分为两个子区间,在左边找,在右边找,接着左右找,这样就能找到要求的结果

典型例题

排序数组

在这里插入图片描述

理解快速排序和归并排序思维的不同点

依旧是经典的排序数组问题,这次选用归并排序来解决,要了解归并排序和快速排序其实都是利用了分治的思想,把一个很复杂的问题分解为一个一个的小问题,二者在思维上有一些小小的区别,快速排序的思想是,对于某个区间来说,把这个区间进行分块,每一个分块都进行排序,每一个都进行排序,这样就完成了目的,这样的思维更像是一种前序遍历,完成了这次的任务后再向后进行延伸,而归并排序的思路和快速排序不同,归并排序的思路主要是把数组拆分成一个一个的小区间,不停的拆分,直到不能拆分后再进行组装,它的排序过程整体上而言是滞后的,更像是一种后序遍历的思想,先一直向深处找,直到找不下去了再进行排序,再一层一层向上走

class Solution 
{vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){if(left>=right){return;}// 数组划分 [left,mid][mid+1,right]int mid=(left+right)/2;// 分块排序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]){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];}}
};

数组中的逆序对

在这里插入图片描述
利用归并排序求逆序对是解决这类问题的常见方法,对于这个题来说,就可以采用分治的方法来解决问题

具体来说,可以把整个问题拆分为几个小步骤,把当前所在区间分成两个区间,在左边的区间内找符合逆序对的对数,再在右边的区间内找符合逆序对的对数,同时把左右两区间都进行排序,这样就可以在左右区间内都寻找符合要求的逆序对数,这就是一个轮回思路,把整个数组拆分为一个一个小区间即可解决问题,这就是分治的思想

那么思路就确认了:

  1. 从左边数组中找符合要求的逆序对
  2. 从右边数组中找符合要求的逆序对
  3. 从左右两边数组中找符合要求的逆序对

从排列组合的分类原理来看,这样就能找到所有的逆序对

从优化角度来讲,第三步是可以进行优化的,这就引入了要排序的原因:

如何从左右两数组中找逆序对数?

其实利用双指针的思想就可以解决,定义cur1和cur2分别指向左右两个数组,假设这里是提前排序好的,升序的数组,那么当cur1所指向的元素大于cur2所指的元素,那么cur2所指向的元素之前的元素全部满足条件,因此一次可以找出很多相同的元素,这也是这个算法的原理

因此这里就引出了为什么要进行排序,左右子区间排序后就可以通过上面的算法快速找到有多少满足要求的逆序对

处理剩余元素

  • 如果是左边出现剩余,说明左边剩下的所有元素都是⽐右边元素⼤的,但是它们都是已经被计算过的,因此不会产⽣逆序对,仅需归并排序即可。

  • 如果是右边出现剩余,说明右边剩下的元素都是⽐左边⼤的,不符合逆序对的定义,因此也不需要处理,仅需归并排序即可。

class Solution 
{vector<int> tmp;
public:    int reversePairs(vector<int>& nums) {tmp.resize(50001);return mergesort(nums,0,nums.size()-1);}int mergesort(vector<int>& nums,int left,int right){if(left>=right){return 0;}int ret=0,mid=(left+right)/2;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]){tmp[i++]=nums[cur1++];}else{ret+=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 ret;}
};

总体来说还是一道有思维量的hard题目,但如果掌握了分治的思想,再去下手就会容易许多

而这样的算法的时间复杂度也是很优秀的,时间复杂度是O(N)

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

在这里插入图片描述

有了上面的题目的思维铺垫,解法还是比较好想的,原理就是利用归并排序进行分治的思想

但这个题和上面的问题也有区别,由于返回的是数组,因此需要记录nums中每一个数组中元素在返回数组中元素的下标,需要一一对应起来,这是比较关键的一步,也就是说,每次找到符合条件的数后,这个数应该被放到返回数组中的哪个位置?这就需要用一个辅助数组来记录原数组中每一个元素的下标所在的位置,这样就能找到了

class Solution 
{vector<int> ret;vector<int> index;int tmpnums[500010];int tmpindex[500010];
public: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 left,int right){if(left>=right){return;}int mid=(left+right)/2;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]){tmpnums[i]=nums[cur2];tmpindex[i++]=index[cur2++];}else{ret[index[cur1]]+=right-cur2+1;tmpnums[i]=nums[cur1];tmpindex[i++]=index[cur1++];}}while(cur1<=mid){tmpnums[i]=nums[cur1];tmpindex[i++]=index[cur1++];}while(cur2<=right){tmpnums[i]=nums[cur2];tmpindex[i++]=index[cur2++];}for(int j=left;j<=right;j++){nums[j]=tmpnums[j-left];index[j]=tmpindex[j-left];}}
};

总结

归并递归解决分治问题主要依托于归并排序,在掌握归并的前提下找到归并过程中要找的关键信息

相关文章:

算法:分治思想处理归并递归问题

文章目录 算法原理实现思路典型例题排序数组数组中的逆序对计算右侧小于当前元素的个数 总结 算法原理 利用归并思想进行分治也是很重要的一种思路&#xff0c;在解决逆序对的问题上有很大的需求空间 于是首先归并排序是首先的&#xff0c;归并排序要能写出来&#xff1a; c…...

小白学Go 基础02-了解Go语言的诞生与演进

Go语言诞生于何时&#xff1f;它的最初设计者是谁&#xff1f;它为什么被命名为Go&#xff1f;它的设计目标是什么&#xff1f;它如今发展得怎么样&#xff1f;带着这些问题&#xff0c;我们一起穿越时空&#xff0c;回到2007年9月Go语言诞生的那一历史时刻吧。 Go语言的诞生 …...

python中如何将十进制转成二进制

python中如何将十进制转成二进制 在 Python 中&#xff0c;你可以使用内置的 bin() 函数将十进制数转换为二进制表示形式。以下是使用 bin() 函数进行转换的示例&#xff1a; decimal_number 10binary_number bin(decimal_number)print(binary_number) # 输出&#xff1a;…...

数据结构--5.0.1图的存储结构

目录 一、邻接矩阵&#xff08;无向图&#xff09; 二、邻接矩阵&#xff08;有向图&#xff09; 三、邻接矩阵&#xff08;网&#xff09; 四、邻接表&#xff08;无向图&#xff09; 五、邻接表&#xff08;有向图&#xff09; ——图的存储结构相比较线性表与树来说就复…...

解决win10 wsl子系统安装的ubuntu环境中lsof,netstat命令查看端口没有任何输出的问题

最近有个以前的ssm项目需要在新电脑上运行测试一下&#xff0c;发现需要redis环境&#xff0c;看了官网说&#xff1a;有两种选择&#xff1a; 1. 要么在虚拟机比如vmware安装linux基础环境&#xff0c;然后再安装redis 2. 要么可以利用win10的wsl linux子系统安装ubuntu&…...

【OpenFeign】OpenFeign结合Hystrix和Sentinel实现熔断降级

OpenFeign可以与Hystrix和Sentinel结合使用&#xff0c;实现降级和熔断。 OpenFeign与Hystrix结合使用 使用OpenFeign需要引入OpenFeign的依赖&#xff1a; <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-sta…...

软件工程(十) 需求工程之需求开发与管理

前面我们学习到了需求工程的概念与分类,我们知道了需求工程主要分为需求开发和需求管理,但是没有说明到底该如何开发需求,有哪些方法去开发需求。到底该如何进行需求管理,又有哪些进行需求管理的方式。具体是如何去做的。下面我们将会详细进行描述。 1、需求开发 1.1、需…...

C++网狐服务器引入开源日志库spdlog

很多人对日志库不以为然&#xff0c;包括网狐这种十几年的公司都不重视&#xff0c;其实日志库记录的东西能在线上出问题时高效解决&#xff0c;特别是别人写的东西&#xff0c;人又走了&#xff0c;出了问题&#xff0c;还可以用日志分析快速解决。要是没有日志记录&#xff0…...

【C++】—— c++11之智能指针

前言&#xff1a; 本期&#xff0c;我们将要学习的是在c11中新提出的概念——异常指针&#xff01; 目录 &#xff08;一&#xff09;智能指针的引入 &#xff08;二&#xff09;内存泄漏 1、什么是内存泄漏&#xff0c;内存泄漏的危害 2、内存泄漏分类&#xff08;了解&a…...

html5——前端笔记

html 一、html51.1、理解html结构1.2、h1 - h6 (标题标签)1.3、p (段落和换行标签)1.4、br 换行标签1.5、文本格式化1.6、div 和 span 标签1.7、img 图像标签1.8、a 超链接标签1.9、table表格标签1.9.1、表格标签1.9.2、表格结构标签1.9.3、合并单元格 1.10、列表1.10.1、ul无序…...

如何在 Vue TypeScript 项目使用 emits 事件

Vue是构建出色的Web应用程序的最灵活、灵活和强大的JavaScript框架之一。Vue中最重要的概念和关键特性之一是能够促进应用程序组件之间的通信。让我们深入探讨一下Vue中的“emits”概念&#xff0c;并了解它们如何以流畅和无缝的方式实现父子组件之间的通信。 Vue中的emits是什…...

文件操作 黑马教程(04)

1.文本文件 写文件 #include "iostream" #include "fstream" using namespace std; /** 文件操作** 程序运行时产生的数据都属于临时数据&#xff0c;程序一旦结束都会被释放* 通过文件可以将数据持久化* C中对文件操作需要包含头文件<fstream>** 文…...

Jmeter(二十七):BeanShell PostProcessor跨线程全局变量使用

在性能测试中&#xff0c;两个相关联的接口不一定都在同一个线程组&#xff0c;遇见这种情况时&#xff0c;我们要进行跨线程组传参&#xff0c;此处用登录和查询配送单两个请求举例&#xff1b; 1、登录请求中配置json提取器&#xff0c;将接口返回的token保存在变量中&#…...

手写表格OCR识别并与大模型ChatGPT交互?

这是一张手写表格&#xff0c;姓名做了脱敏处理。现在需要对其识别&#xff0c;并分析。 直接粘贴剪切板中的表格原始图片&#xff0c;在网页中ctlV进行识别。识别结果列用分隔符|&#xff0c;可以直接粘贴到excel&#xff0c;进行数据列分隔。为了美观期间&#xff0c;也可以用…...

使用 v-for 指令和数组来实现在 Uni-app 中动态增减表单项并渲染多个数据

在 data 中定义一个数组&#xff0c;用于存储表单项的数据&#xff1a; data() {return {formItems: []} } 在模板中使用 v-for 指令渲染表单项&#xff1a; <template><div><div v-for"(item, index) in formItems" :key"index"><…...

xml

1.xml 1.1概述【理解】 万维网联盟(W3C) 万维网联盟(W3C)创建于1994年&#xff0c;又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。 建立者&#xff1a; Tim Berners-Lee (蒂姆伯纳斯李)。 是Web技术领域最具权威和影响力的国际中立性技术标准机构。 到目前为…...

Java中的动态代理(JDK Proxy VS CGLib)

前言 动态代理可以说是Java基础中一个比较重要的内容&#xff0c;这块内容关系到Spring框架中的AOP实现原理&#xff0c;所以特别写了一篇作为个人对这块知识的总结。这部分内容主要包括&#xff1a;JDK Proxy和CGLib的基本介绍、二者的实现原理、代码示例等。 什么是动态代理…...

Redis 7 第七讲 哨兵模式(sentinal)

哨兵模式 哨兵巡查监控后台master主机是否故障,如果出现故障根据投票时自动将某一个从库转换成新的主库,继续对外服务。 作用 1. 监控redis运行状态,包括master和slave 2. 当master down机,能自动将salve切换成新的master 应用场景 主从监控监控主从redis库运行的状态…...

Python入门教程 - 判断语句(二)

目录 一、布尔类型 二、比较运算符 三、if判断语句 一、布尔类型 True False result1 10 > 5 result2 10 < 5 print(result1) print(result2) print(type(result1)) True False <class bool> 二、比较运算符 ! > < > < 比较运算的结果是布尔…...

LeetCode-55-跳跃游戏-贪心

题目描述&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 解…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...