算法:分治(归并)题目练习

目录

题目一:排序数组

题目二:数组中的逆序对

题目三:计算右侧小于当前元素的个数

题目四:翻转对


题目一:排序数组

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

归并排序也就是找一个中间值mid,先排mid左边的区域,再排mid右边的区域,而左边的区域又可以分为两块,继续排序,以此类推 .....最后再将两个有序数组进行合并

这里的归并排序与上一章节的快排,都是执行了数组分块的逻辑,较为类似,所以放在一块讲解

这里可以将快排理解为二叉树的前序遍历,即先将根结点这一层分好,再去分左子树,右子树...

而归并排序,可以理解为二叉树的后序遍历,即先将左子树、右子树分完,再合并到根结点处

这里的归并排序同样分为下面几步:

①选择中间点mid
②左右区间排序
③合并左右两个数组
④将 tmp 数组数据还原到数组 nums 中


代码如下:

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;//选择中间点划分int mid = ((right - left) >> 1) + left;//左右区间排序mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//合并两个数组int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : 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];}
};

题目二:数组中的逆序对

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

示例 1:

输入:record = [9, 7, 5, 4, 6]
输出:8
解释:交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

逆序对其实在大学的课程是学过的,只要在数组中从前往后挑选的两个数中,前一个数比后一个数大,就称这两个数为一个逆序对

解法一:暴力解法

两层for循环,依次枚举每一个组合,从所有组合中寻找逆序对,这种解法比较简单,且一定会超时,所以代码就不列举了

解法二:归并排序

下面可以对归并排序说明,即分为两部分,左边部分挑出来逆序对个数,右边部分挑出来逆序对个数,再一左一右挑出来逆序对个数,相加即可

下面可以优化为:

左半部分 -> 左排序 -> 右半部分 -> 右排序 -> 一左一右 -> 排序

策略一:找出该数之前,有多少个数比我大的(升序排列)

现在分为两部分,如下所示:

因为是升序排序的,所以此时cur1、cur2前面的部分都是小的,由于要找的逆序对时前面的数比后面的数大,所以当找到cur1大于cur2的时候,左半部分的cur1后面的其他数也肯定大于cur2,此时就不用继续比较了,直接加上后面的个数,再cur2++,往后寻找,也就是:

①nums[cur1] <= nums[cur2]:cur1++
②nums[cur] > nums[cur2]:ret += mid - cur1 + 1,cur2++


策略二:找出该数之后,有多少个数比我小的(降序排列)

降序排列如下所示:

①nums[cur2] < nums[cur1]:ret += right - (mid + 1) +1 = right - mid,cur1++
②nums[cur2] >= nums[cur1]:cur2++


代码如下:

class Solution 
{vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergeSort(record, 0, record.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;//找中间点,将数组分为两部分int mid = ((right - left) >> 1) + left;//左边数组 + 排序 + 右边数组 + 排序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 && cur2 <= right)// {//     if(nums[cur1] > nums[cur2])//     {//         ret += right - cur2 + 1;//         tmp[i++] = nums[cur1++];//     }//     else//     {//         tmp[i++] = nums[cur2++];//     }// }while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//还原数组for(i = left; i <= right; i++) nums[i] = tmp[i - left];return ret;}
};

题目三:计算右侧小于当前元素的个数

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

示例 1:

输入:nums = [5,2,6,1]
输出:[2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2:

输入:nums = [-1]
输出:[0]

示例 3:

输入:nums = [-1,-1]
输出:[0,0]

这道题与上一道题的逆序对比较像,上一题是直接求逆序对的数量,而此题是求每个元素有几个右边比它小的元素的数量

解法:归并排序(分治)

上一题讲到了有两个策略:

策略一:求一个数左边有多少个数比我大(升序)

策略二:求一个数右边有多少个数比我小(降序)

此题使用策略二比较方便些,图如下所示:

所以就有下面两种情况:

①nums[cur1] <= nums[cur2]:cur2++
②nums[cur1] > nums[cur2]:数组中cur1这个位置的数 = 原始下标 + right - cur2 + 1

那么由于归并排序是会改变数组中元素位置的,怎么能够记住数组中原始下标的位置呢?

利用哈希的思想, 创建一个和nums等规模大小的数组,并记录原始的下标,在nums数组的元素移动时,该数组也跟着移动即可

由于此时多了一个index下标数组,所以还需要多创建一个辅助数组,需要注意的是在使用nums数组的辅助数组tmpNums时,index数组的辅助数组tmpIndex也需要使用,为了最终能够找到原始下标

在处理一左一右两部分时,由于需要记录cur1位置的数值,那么就需要该位置的数值所对应的原始下标,原始下标为index[cur1],找到了原始下标,那么此时往最终的数组中写时,就变为了:
ret[index[cur1]]


代码如下:

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); //初始化 index 数组for(int i = 0; i < n; i++) index[i] = i;mergeSort(nums, 0, nums.size() - 1);return ret;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;int mid = ((right - left) >> 1) + left;//先处理左右两部分//[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]){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 i = left; i <= right; i++){nums[i] = tmpNums[i - left];index[i] = tmpIndex[i - left];}}
};

题目四:翻转对

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

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

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

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

这道题和逆序对那道题非常相似,逆序对是求前面的数大于后面的数的个数,而这道题是求前面的数大于后面数的两倍的个数

解法一:暴力枚举

暴力枚举就是固定一个数,枚举后面的数,以此类推,找到符合条件组合的个数,时间一定会超时,就不多说了,看下面的解法

解法二:分治

讲一个数组分为两部分,先求左边的翻转对的个数,再求右边翻转对的个数,再求一左一右的翻转对的个数

那么接下来,需要考虑怎么使用归并,能够解决此题

依旧是两种策略:

策略一:计算当前元素后面,有多少元素的2倍比我小(降序)

策略二:计算当前元素前面,有多少元素的一半比我大(升序)

与前面的计算方式不同的是,逆序对那道题,由于与递归排序的 if 语句中的判断条件是一样的,都是 nums[cur1] 与 nums[cur2] 比较,所以可以在递归的过程中,进行 ret++

而这道题是 nums[cur1] 与 2 * nums[cur2] 进行比较,不同的判断条件可能会导致遗漏,

所以在归并之前,先来判断这种情况有多少个翻转对,如果采用的是策略一,就让 ret += right - cur2 + 1,直到 cur1 <= mid 这个判断条件结束,下面再进行这一次的归并排序,以此类推


代码如下:

class Solution 
{int tmp[50010]; //辅助数组
public:int reversePairs(vector<int>& nums) {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 = ((right - left) >> 1) + left;//计算左右两侧的翻转对ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//先计算翻转对的数量int cur1 =  left, cur2 = mid + 1, i = 0;while(cur1 <= mid) //降序{while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;if(cur2 > right) break;ret += right - cur2 + 1;cur1++;}//合并两个有序数组cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];}//处理没有处理完毕的数组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;}
};

分治中,关于归并的题目到此结束


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

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

相关文章

python 逻辑控制语句、循环语句

文章目录 一、逻辑控制语句&#xff08;if、elif、else&#xff09;1.1 单个条件的逻辑判断语句1.2 多个条件的逻辑判断语句 二、循环语句2.1 while 循环2.2 for 循环2.2.1 循环使用 else 语句 一、逻辑控制语句&#xff08;if、elif、else&#xff09; Python 条件语句是通过一…

el-date-picker 有效时间精确到时分秒 且给有效时间添加标记

el-date-picker实现有效日期做标记且时分秒限制选择范围 代码如下&#xff1a; // html部分 <el-date-pickerv-model"dateTime"type"datetime":picker-options"pickerOptions" > </el-date-picker>// js部分 /*** 回放有效日期开始时…

24年计算机等级考试22个常见问题解答❗

24年9月计算机等级考试即将开始&#xff0c;整理了报名中容易遇到的22个问题&#xff0c;大家对照入座&#xff0c;避免遇到了不知道怎么办&#xff1f; 1、报名条件 2、报名入口 3、考生报名之后后悔了&#xff0c;不想考了&#xff0c;能否退费&#xff1f; 4、最多能够报多少…

Git进阶使用(图文详解)

文章目录 Git概述Git基础指令Git进阶使用一、Git分支1.主干分支2.其他分支2.1创建分支2.2查看分支1. 查看本地分支2. 查看远程分支3. 查看本地和远程分支4. 显示分支的详细信息5. 查看已合并和未合并的分支 2.3切换分支1. 切换到已有的本地分支2. 创建并切换到新分支3. 切换到远…

2-11 基于matlab的BP-Adaboost的强分类器分类预测

基于matlab的BP-Adaboost的强分类器分类预测&#xff0c;Adaboost是一种迭代分类算法&#xff0c;其在同一训练集采用不同方法训练不同分类器&#xff08;弱分类器&#xff09;&#xff0c;并根据弱分类器的误差分配不同权重&#xff0c;然后将这些弱分类器组合成一个更强的最终…

第二十五篇——信息加密:韦小宝说谎的秘诀

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 加密这件事&#xff0c;对于这个时代的我们来说非常重要&#xff0c;那么…

Redis缓存的一些概念性问题

目录 缓存模型和思路 缓存更新策略 数据库和缓存不一致 缓存与数据库双写一致 缓存穿透 缓存雪崩 缓存击穿 速度快,好用&#xff0c;内存的读写性能远高于磁盘,缓存可以大大降低用户访问并发量带来的服务器读写压力 缓存模型和思路 标准的操作方式就是查询数据库之前先…

scratch编程03-反弹球

这篇文章和上一篇文章《scratch3编程02-使用克隆来编写小游戏》类似&#xff08;已经完全掌握了克隆的可以忽略这篇文章&#xff09;&#xff0c;两篇文章都使用到了克隆来编写一个小游戏&#xff0c;这篇文章与上篇文章不同的是&#xff0c;本体在进行克隆操作时&#xff0c;不…

Solr7.4.0报错org.apache.solr.common.SolrException

文章目录 org.apache.solr.common.SolrException: Exception writing document id MATERIAL-99598435990497269125316 to the index; possible analysis error: cannot change DocValues type from NUMERIC to SORTED_NUMERIC for field "opt_time"Exception writing…

账号和权限的管理

文章目录 管理用户账号和组账号用户账号的分类超级用户普通用户程序用户 UID&#xff08;用户id)和(组账号)GIDUID用户识别号GID组标识号 用户账号文件添加用户账号设置/更改用户口令 管理用户账号和组账号 用户账号的分类 超级用户 root 用户是 Linux 操作系统中默认的超级…

Python学习笔记15:进阶篇(四)文件的读写。

文件操作 学习编程操作中&#xff0c;我觉得文件操作是必不可少的一部分。不管是读书的时候学习的c&#xff0c;c&#xff0c;工作的前学的java&#xff0c;现在学的Python&#xff0c;没学过的php和go&#xff0c;都有文件操作的模块以及库的支持&#xff0c;重要性毫无疑问。…

HCIA-速查-ENSP模拟器2步清空配置

需求&#xff1a;清空模拟器配置 清空当前图中配置 步骤1&#xff1a;reset saved-configuration 后输入y确认 步骤2&#xff1a;reboot后输入n否认再输入y确认 验证已经清空配置

idea http client GET 请求 报503错误

idea 提供的 http client 插件&#xff0c;在 GET 请求时总是 报503 的错误&#xff0c;但请求URL可以在浏览器中正常访问。 GET localhost:8080/student Response file saved. > 2024-06-20T160906.503.html 有一种原因跟本地配置的代理有关&#xff0c;如下图。如果在…

基于JSP的高校信息资源共享平台

开头语&#xff1a; 你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果你对高校信息资源共享平台感兴趣或者有相关需求&#xff0c;可以通过文末的联系方式找到我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;JSP技术 工具&#xff1a;IDEA…

Java23种设计模式(五)

1、MVC 模式 MVC 模式代表 Model-View-Controller&#xff08;模型-视图-控制器&#xff09; 模式。这种模式用于应用程序的分层开发。 Model&#xff08;模型&#xff09; - 模型代表一个存取数据的对象或 JAVA POJO。它也可以带有逻辑&#xff0c;在数据变化时更新控制器。…

前缀和+双指针,CF 131F - Present to Mom

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 131F - Present to Mom 二、解题报告 1、思路分析 很经典的一种把列看作cell 来进行双指针/递推的题型 我们考虑&#xff0c;可以预处理出原矩阵中的所有star 然后我们去枚举矩形的上下边界&#xff0c;把…

python:faces swap

# encoding: utf-8 # 版权所有 2024 涂聚文有限公司 # 许可信息查看&#xff1a;pip install boost # 描述&#xff1a;pip install boost # pip install dlib # pip install cmake3.25.2 # pip install dlib19.24.2 如果安装不上&#xff0c;按此法 # Author : geovindu,G…

【Go】用 DBeaver、db browser 和 SqlCipher 读取 SqlCipher 数据库

本文档主要描述如何用 DBeaver、db browser 和 SqlCipher 上打开加密的 SQLite3 数据库(用 SqlCipher v3 加密) 软件版本 DBeaver&#xff1a;v24.1.0 SQLite-driver: sqlite-jdbc-3.46.0.0.jar dbbrowser-for-sqlite-cipher&#xff1a;3.12.2 SqlCipher cli(ubuntun)&am…

基于Windows API DialogBox的对话框

在C中&#xff0c;DialogBox函数是Windows API的一部分&#xff0c;它用于在Win32应用程序中创建并显示一个模态对话框。DialogBox函数是USER32.DLL中的一个导出函数&#xff0c;因此你需要在你的C Win32应用程序中链接到这个库。 #include "framework.h" #include …

反转链表(java精简版)

反转一个单向链表。 public class ReversingLinkedList {static class Node {int val;Node next;public Node(int val) {this.val val;}public boolean hasNext() {return next ! null;}}public static void main(String[] args) {//构造Node head null;Node shift null;for…