devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：黑客灵魂 | 2024-06-21 14:44:27

赞

踩

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

目录

题目一：排序数组

题目二：数组中的逆序对

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

题目四：翻转对

题目一：排序数组

给你一个整数数组 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 中

代码如下：

  1. class Solution 
  2. {
  3.     vector<int> tmp;//临时数组放全局，相比于放局部提高效率
  4. public:
  5.     vector<int> sortArray(vector<int>& nums) 
  6.     {
  7.         tmp.resize(nums.size());//临时数组 开空间 + 初始化
  8.         mergeSort(nums, 0, nums.size() - 1);
  9.         return nums;
  10.     }
  11.  
  12.     void mergeSort(vector<int>& nums, int left, int right)
  13.     {
  14.         if(left >= right) return;
  15.         //选择中间点划分
  16.         int mid = ((right - left) >> 1) + left;
  17.         //左右区间排序
  18.         mergeSort(nums, left, mid);
  19.         mergeSort(nums, mid + 1, right);
  20.         //合并两个数组
  21.         int cur1 = left, cur2 = mid + 1, i = 0;
  22.         while(cur1 <= mid && cur2 <= right)
  23.             tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
  24.         //处理两个数组中可能有剩余元素的数组，即没有遍历完的数组
  25.         while(cur1 <= mid) tmp[i++] = nums[cur1++]; 
  26.         while(cur2 <= right) tmp[i++] = nums[cur2++];
  27.         //还原数组
  28.         for(int i = left; i <= right; i++) nums[i] = tmp[i - left];
  29.     }
  30. };

题目二：数组中的逆序对

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 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++

代码如下：

  1. class Solution 
  2. {
  3.     vector<int> tmp;
  4. public:
  5.     int reversePairs(vector<int>& record) 
  6.     {
  7.         tmp.resize(record.size());
  8.         return mergeSort(record, 0, record.size() - 1);
  9.     }
  10.  
  11.     int mergeSort(vector<int>& nums, int left, int right)
  12.     {
  13.         if(left >= right) return 0;
  14.  
  15.         int ret = 0;
  16.         //找中间点，将数组分为两部分
  17.         int mid = ((right - left) >> 1) + left;
  18.         //左边数组 + 排序 + 右边数组 + 排序
  19.         ret += mergeSort(nums, left, mid);
  20.         ret += mergeSort(nums, mid + 1, right);
  21.         //一左一右的数
  22.         int cur1 = left, cur2 = mid + 1, i = 0;
  23.         //策略一：升序版本
  24.         while(cur1 <= mid && cur2 <= right)
  25.         {
  26.             if(nums[cur1] <= nums[cur2])
  27.             {
  28.                 tmp[i++] = nums[cur1++];
  29.             }
  30.             else
  31.             {
  32.                 ret += mid - cur1 + 1;
  33.                 tmp[i++] = nums[cur2++];
  34.             }
  35.         }
  36.         //策略二：降序版本
  37.         // while(cur1 <= mid && cur2 <= right)
  38.         // {
  39.         //     if(nums[cur1] > nums[cur2])
  40.         //     {
  41.         //         ret += right - cur2 + 1;
  42.         //         tmp[i++] = nums[cur1++];
  43.         //     }
  44.         //     else
  45.         //     {
  46.         //         tmp[i++] = nums[cur2++];
  47.         //     }
  48.         // }
  49.         while(cur1 <= mid) tmp[i++] = nums[cur1++];
  50.         while(cur2 <= right) tmp[i++] = nums[cur2++];
  51.         //还原数组
  52.         for(i = left; i <= right; i++) nums[i] = tmp[i - left];
  53.         return ret;
  54.     }
  55. };

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

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

示例 1：

输入：nums = [5,2,6,1]
输出：
  1. [2,1,1,0] 
  2. 解释：

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]]

代码如下：

  1. class Solution 
  2. {
  3.     vector<int> ret;      //最终结果
  4.     vector<int> index;    //原始下标
  5.     int tmpNums[500010];  //辅助数组
  6.     int tmpIndex[500010]; //辅助数组
  7. public:
  8.     vector<int> countSmaller(vector<int>& nums) 
  9.     {
  10.         int n = nums.size();
  11.         ret.resize(n), index.resize(n); 
  12.         //初始化 index 数组
  13.         for(int i = 0; i < n; i++) index[i] = i;
  14.         mergeSort(nums, 0, nums.size() - 1);
  15.         return ret;
  16.     }
  17.  
  18.     void mergeSort(vector<int>& nums, int left, int right)
  19.     {
  20.         if(left >= right) return;
  21.  
  22.         int mid = ((right - left) >> 1) + left;
  23.         //先处理左右两部分
  24.         //[left, mid] [mid + 1, right]
  25.         mergeSort(nums, left, mid);
  26.         mergeSort(nums, mid + 1, right);
  27.         //处理一左一右两部分
  28.         int cur1 = left, cur2 = mid + 1, i = 0;
  29.         while(cur1 <= mid && cur2 <= right)
  30.         {
  31.             if(nums[cur1] <= nums[cur2])
  32.             {
  33.                 tmpNums[i] = nums[cur2];
  34.                 tmpIndex[i++] = index[cur2++];
  35.             }
  36.             else
  37.             {
  38.                 ret[index[cur1]] += right - cur2 + 1;
  39.                 tmpNums[i] = nums[cur1];
  40.                 tmpIndex[i++] = index[cur1++];
  41.             }
  42.         }
  43.         //处理可能没处理完的排序过程
  44.         while(cur1 <= mid)
  45.         {
  46.             tmpNums[i] = nums[cur1];
  47.             tmpIndex[i++] = index[cur1++];
  48.         }
  49.         while(cur2 <= right)
  50.         {
  51.             tmpNums[i] = nums[cur2];
  52.             tmpIndex[i++] = index[cur2++];
  53.         }
  54.         //还原数组
  55.         for(int i = left; i <= right; i++)
  56.         {
  57.             nums[i] = tmpNums[i - left];
  58.             index[i] = tmpIndex[i - left];
  59.         }
  60.     }
  61. };

题目四：翻转对

给定一个数组 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 这个判断条件结束，下面再进行这一次的归并排序，以此类推

代码如下：

  1. class Solution 
  2. {
  3.     int tmp[50010]; //辅助数组
  4. public:
  5.     int reversePairs(vector<int>& nums) 
  6.     {
  7.         return mergeSort(nums, 0, nums.size() - 1);
  8.     }
  9.  
  10.     int mergeSort(vector<int>& nums, int left, int right)
  11.     {
  12.         if(left >= right) return 0;
  13.         int ret = 0;
  14.         //根据中间元素划分区间
  15.         int mid = ((right - left) >> 1) + left;
  16.         //计算左右两侧的翻转对
  17.         ret += mergeSort(nums, left, mid);
  18.         ret += mergeSort(nums, mid + 1, right);
  19.         //先计算翻转对的数量
  20.         int cur1 =  left, cur2 = mid + 1, i = 0;
  21.         while(cur1 <= mid) //降序
  22.         {
  23.             while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
  24.             if(cur2 > right) break;
  25.             ret += right - cur2 + 1;
  26.             cur1++;
  27.         }
  28.         //合并两个有序数组
  29.         cur1 = left, cur2 = mid + 1;
  30.         while(cur1 <= mid && cur2 <= right)
  31.         {
  32.             tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
  33.         }
  34.         //处理没有处理完毕的数组
  35.         while(cur1 <= mid) tmp[i++] = nums[cur1++];
  36.         while(cur2 <= right) tmp[i++] = nums[cur2++];
  37.         //恢复数组
  38.         for(int i = left; i <= right; i++) nums[i] = tmp[i - left];
  39.         return ret;
  40.     }
  41. };

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/743381
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号