分治精炼宝库----归并排序应用( ´◔︎ ‸◔︎`)

2024-06-23 15:36

本文主要是介绍分治精炼宝库----归并排序应用( ´◔︎ ‸◔︎`),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一.基本概念:

二.归并排序:

 三.交易逆序对总数:

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

五.翻转对:

 六.合并k个有序链表:


一.基本概念:

🐻在计算机科学中,分治法是一种很重要的算法。字面上的解释就是“分而治之”,就是把一个复杂的问题分成两个或则更多个相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。🧐分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

当我们对分治算法有了以上的一定了解后,来联系几道题目加深理解~~

二.归并排序:

归并排序的流程充分的体现了「分⽽治之」的思想,⼤体过程分为两步:

  • 分:将数组⼀分为⼆为两部分,⼀直分解到数组的⻓度为1 ,使整个数组的排序过程被分为 「左半部分排序」+「右半部分排序」;
  • 治:将两个较短的「有序数组合并成⼀个⻓的有序数组」,⼀直合并到最初的⻓度。

大致图解过程(图中例子为主):

 咱们以leetcode排序数组题目为例:912. 排序数组 - 力扣(LeetCode)

代码详解:

class Solution {int[] tmp;public int[] sortArray(int[] nums) {int n = nums.length;tmp = new int[n];mergeSort(nums,0,n - 1);return nums;}public void mergeSort(int[] nums,int left,int right){if(left >= right) return ;//取中点划分区域//[left,mid] [mid + 1,right];int mid = left + (right - left) / 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 j = left;j <= right;j++){nums[j] = tmp[j - left];}}}

我们提取一下主要框架,大致就是:

 看这个框架,也就明白那句经典的总结:归并排序就是先把左半边数组排好序,再把右半边数组排好序,然后把两半数组合并。

运行结果:

 三.交易逆序对总数:

题目链接:LCR 170. 交易逆序对的总数 - 力扣(LeetCode)

题目描述:

在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record,返回其中存在的「交易逆序对」总数。

算法思路: 

如果我们将数组从中间划分成两个部分,那么我们可以将逆序对产⽣的⽅式划分成三组:

  • 逆序对中两个元素:全部从左数组中选择
  • 逆序对中两个元素:全部从右数组中选择
  • 逆序对中两个元素:⼀个选左数组另⼀个选右数组

根据排列组合的分类相加原理,这三种情况下的逆序对总和,就是总的逆序对总和。不难发现,这其实和归并排序的主过程一致,所以我们可以利用归并排序的特性,先计算左半部分数组的逆序对,再计算右半部分数组的逆序对数,最后计算一左一右的逆序对个数。三者相加,就是总的逆序对个数。

合并操作时,计算一左一右的逆序对个数:

此时mergeSort(nums,0,nums.length - 1) 就有了新的定义,计算并返回数组区间[0 , nums.length - 1] 的逆序对个数

代码详解:

class Solution {int[] tmp;public int reversePairs(int[] record) {int n = record.length;tmp = new int[n];return mergeSort(record,0,n - 1);}public int mergeSort(int[] nums,int left,int right){if(left >= right) return 0;//取中间点划分区间int mid = left + (right - left)/ 2;//[left,mid][mid + 1,right];int res = 0;//记录结果res += mergeSort(nums,left,mid);res += 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{res += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}//处理没有完全合并的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//还原数组for(int j = left;j <= right;j++){nums[j] = tmp[j - left];}return res;}
}

运行结果:

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

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

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

算法思路:

这⼀道题的解法与求数组中的逆序对的解法是类似的,但是这⼀道题要求的不是求总的个数,⽽ 是要返回⼀个数组,记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩。 但是在我们归并排序的过程中,元素的下标是会跟着变化的,因此我们需要⼀个辅助数组,来将数 组元素和对应的下标绑定在⼀起归并,也就是再归并元素的时候,顺势将下标也转移到对应的位置 上。由于我们要快速统计出某⼀个元素后⾯有多少个⽐它⼩的,所以我们采用降序策略:

 代码详解:

class Solution {int[] tmp1;int[] tmp2;int[] index;//记录数组下标位置int[] res;//记录结果List<Integer> ret = new ArrayList<>();//记录返回结果public List<Integer> countSmaller(int[] nums) {int n = nums.length;tmp1 = new int[n];tmp2 = new int[n];res = new int[n];index = new int[n];//初始化坐标位置for(int i = 0;i < n;i++) index[i] = i;mergeSort(nums,0,n - 1);for(int i = 0;i < n;i++) ret.add(res[i]);return ret;}public void mergeSort(int[] nums,int left,int right){if(left >= right) return ;//取中间划分区域int mid = left + (right - left) / 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]){tmp1[i] = nums[cur2];tmp2[i++] = index[cur2++];}else{res[index[cur1]] += right - cur2 + 1;tmp1[i] = nums[cur1];tmp2[i++] = index[cur1++];}}//处理没有完全合并的数组while(cur1 <= mid){tmp1[i] = nums[cur1];tmp2[i++] = index[cur1++];}while(cur2 <= right){tmp1[i] = nums[cur2];tmp2[i++] = index[cur2++];}//还原数组for(int j = left;j <= right;j++){nums[j] = tmp1[j - left];index[j] = tmp2[j - left];}}
}

运行结果:

五.翻转对:

题目链接:493. 翻转对 - 力扣(LeetCode)

题目描述:

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

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

算法思路:

大思路与求逆序对的思路一样,就是利用归并排序的思想,将求整个数组的翻转对的数量,转化成三部分:左半区间翻转对的数量,右半区间翻转对的数量,一左一右选择时翻转对的数量。重点实在合并过程中,如何计算出翻转对的数量。与上个问题不同的是,上一道题我们可以一边合并一边计算结果,但是这道题左边元素大于右边元素的两倍的条件不符合归并排序时的特性,如果我们直接合并,是无法计算出翻转对的个数的,因此我们要再归并排序的合并之前,排序之后完成对翻转对的统计。

代码详解:

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return mergeSort(nums,0,n - 1);}public int mergeSort(int[] nums,int left,int right){if(left >= right) return 0;//取中间点划分区间int mid = left + (right - left) / 2;int res = 0;//记录结果//[left,mid] [mid + 1,right]res += mergeSort(nums,left,mid);res += mergeSort(nums,mid + 1,right);int cur1 = left,cur2 = mid + 1,i = 0;//计算翻转对while(cur1 <= mid){//注意处理越界情况while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;if(cur2 > right){break;}res += right - cur2 + 1;cur1++;}//合并有序数组cur1 = left;cur2 = mid + 1;//重置一下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 j = left;j <= right;j++){nums[j] = tmp[j - left];}//返回结果return res;} 
}

运行结果:

 六.合并k个有序链表:

题目链接:23. 合并 K 个升序链表 - 力扣(LeetCode)

题目描述:

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

  • 解法一:分治 

思路:与归并排序数组一样的原理,只不过这里的合并过程是合并两个有序链表,而排序数组是合并两个有序数组。

代码详解:

class Solution {ListNode[] tmp;public ListNode mergeKLists(ListNode[] lists) {if(lists.length == 0) return null;return mergeSort(lists,0,lists.length - 1);}public ListNode mergeSort(ListNode[] lists,int left,int right){if(left >= right) return lists[left];//取中间节点划分两部分int mid = (left + right) / 2;//[left,mid] [mid + 1,right]ListNode l1 =  mergeSort(lists,left,mid);ListNode l2 = mergeSort(lists,mid + 1,right);//合并两个有序链表return merge(l1,l2);}public ListNode merge(ListNode l1,ListNode l2){if(l1 == null) return l2;if(l2 == null) return l1;ListNode cur1 = l1,cur2 = l2;ListNode res = new ListNode(-1);//虚拟节点ListNode pre = res;while(cur1 != null && cur2 != null){if(cur1.val <= cur2.val){pre.next = cur1;pre = cur1;cur1 = cur1.next;}else{pre.next = cur2;pre = cur2;cur2 = cur2.next;}}if(cur1 != null) pre.next = cur1;if(cur2 != null) pre.next = cur2;return res.next;}}
  • 解法二:利用数据结构---堆

算法思路:

合并K 个升序链表时,我们依旧可以选择K 个链表中,头结点值最⼩的那⼀个。那么如何快速的得 到头结点最⼩的是哪⼀个呢?⽤堆这个数据结构就好啦~ 我们可以把所有的头结点放进⼀个⼩根堆中,这样就能快速的找到每次K 个链表中,最⼩的元素是哪 个。然后我们取出最小的节点合并,再将其后面一个位置的索引丢入到小根堆中。

代码详解:

class Solution {public ListNode mergeKLists(ListNode[] lists) {//定义一个优先级队列,排序规则是从小到大PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)-> v1.val - v2.val);//将所有头节点放入到优先级队列中for(ListNode head : lists){if(head != null){heap.offer(head);}}//合并链表ListNode res = new ListNode(-1);//虚拟节点ListNode pre = res;while(!heap.isEmpty()){ListNode t = heap.poll();pre.next = t;pre = t;if(t.next != null) heap.offer(t.next);}return res.next;}
}

参考资料:

 五大常用算法之一:分治算法 - Will_Don - 博客园 (cnblogs.com)

《labuladong算法笔记》

封面来自:《hello 算法》

结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!

这篇关于分治精炼宝库----归并排序应用( ´◔︎ ‸◔︎`)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的?mac系统中有很多自带的应用,想要看看哪些是系统自带,该怎么查看呢?下面我们就来看看Mac系统内... 在MAC电脑上,可以使用以下方法来确定哪些软件是系统自带的:1.应用程序文件夹打开应用程序文件夹

Python Flask 库及应用场景

《PythonFlask库及应用场景》Flask是Python生态中​轻量级且高度灵活的Web开发框架,基于WerkzeugWSGI工具库和Jinja2模板引擎构建,下面给大家介绍PythonFl... 目录一、Flask 库简介二、核心组件与架构三、常用函数与核心操作 ​1. 基础应用搭建​2. 路由与参

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,:本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总

电脑系统Hosts文件原理和应用分享

《电脑系统Hosts文件原理和应用分享》Hosts是一个没有扩展名的系统文件,当用户在浏览器中输入一个需要登录的网址时,系统会首先自动从Hosts文件中寻找对应的IP地址,一旦找到,系统会立即打开对应... Hosts是一个没有扩展名的系统文件,可以用记事本等工具打开,其作用就是将一些常用的网址域名与其对应

CSS 样式表的四种应用方式及css注释的应用小结

《CSS样式表的四种应用方式及css注释的应用小结》:本文主要介绍了CSS样式表的四种应用方式及css注释的应用小结,本文通过实例代码给大家介绍的非常详细,详细内容请阅读本文,希望能对你有所帮助... 一、外部 css(推荐方式)定义:将 CSS 代码保存为独立的 .css 文件,通过 <link> 标签

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Python使用Reflex构建现代Web应用的完全指南

《Python使用Reflex构建现代Web应用的完全指南》这篇文章为大家深入介绍了Reflex框架的设计理念,技术特性,项目结构,核心API,实际开发流程以及与其他框架的对比和部署建议,感兴趣的小伙... 目录什么是 ReFlex?为什么选择 Reflex?安装与环境配置构建你的第一个应用核心概念解析组件

C#通过进程调用外部应用的实现示例

《C#通过进程调用外部应用的实现示例》本文主要介绍了C#通过进程调用外部应用的实现示例,以WINFORM应用程序为例,在C#应用程序中调用PYTHON程序,具有一定的参考价值,感兴趣的可以了解一下... 目录窗口程序类进程信息类 系统设置类 以WINFORM应用程序为例,在C#应用程序中调用python程序