算法 --- 分治（归并）

分治（归并）

分治（特别是归并）算法适用于解决“整体求解依赖于子问题合并”且子问题相互独立的题目，其典型特征是能将大规模数据分解、递归求解，然后通过合并操作（这正是归并排序中‘归并’的精髓）来构建最终答案。

什么样的题目适用于分治（归并）算法？

判断一个题目是否适用分治（归并）算法，主要看它是否满足以下三个核心条件，尤其是第三个“合并”步骤：

1. 可分解性：问题能够被递归地分解成若干个规模更小、结构相同的子问题。

   • 例子： 对一个数组排序，可以分解为对左半部分和右半部分分别排序。

2. 子问题独立性：分解出的子问题之间是相互独立的，解决其中一个不会影响另一个。

   • 这是分治与动态规划（DP）的关键区别。DP的子问题是重叠的，需要记忆化。

3. 可合并性（最关键）：问题的解能够通过合并所有子问题的解来高效地得到。

   • 这是“归并”思想的体现。 合并过程往往不是简单的相加，而是需要一个精心设计的算法步骤。

常见的题目类型（不仅仅是排序）

基于以上特点，分治（归并）算法主要适用于以下几类题目：

1. 分治排序与选择

这是最经典的应用，直接体现了“分治”和“归并”的思想。

• 归并排序：将数组分成两半，分别排序后，再合并两个有序数组。

• 快速排序：也是一种分治，但核心是“划分”而非“归并”。

• 求逆序对：在归并排序的合并过程中，可以高效地统计出跨越左右两个子数组的逆序对数量，这是分治法的典范应用。

2. 大规模计算与统计问题

当问题需要处理大规模数据（如数组、矩阵）并计算某种聚合关系时，分治非常有效。

• 计算右侧小于当前元素的个数：与求逆序对思路类似，在归并排序的同时记录答案。

• 区间和的统计问题：例如，给定数组，求有多少个连续子数组的和在某个范围内。可以通过“归并排序求前缀和数组”的方式来解决。

3. 高级数据结构相关

许多高效的数据结构其底层操作就是分治。

• 线段树：构建、查询、更新操作都是典型的分治（一分为二）。

• 字典树、堆等结构的某些操作也蕴含分治思想。

4. 树与图的相关问题

树结构本身就是一个递归（分治）结构。

• 树的遍历：前序、中序、后序遍历本身就是“先处理左子树（子问题1），再处理右子树（子问题2），最后处理根（合并）”的分治过程。

• 最近公共祖先等问题常用分治思想解决。

5. 数学计算问题

一些经典算法本身就是分治。

• 大整数乘法（Karatsuba算法）：将大数分成小块进行计算后再合并。

• 快速傅里叶变换：通过分治将多项式系数表示法转换为点值表示法，极大加速了卷积运算。

总结：一个简单的判断方法

当你看到一个题目时，可以问自己：
“如果我把输入数据分成两半，分别求出两半的答案，我能否有效地通过这两个答案推导出整个问题的答案？”

如果答案是肯定的，并且子问题可以继续这样分解下去，那么这个问题就非常适合用分治（归并）算法来解决。其中，“有效地推导”这个过程就是“归并”操作的核心。

题目练习

912. 排序数组 - 力扣（LeetCode）

解法（归并排序）：

算法思路：

归并排序的流程充分的体现了「分而治之」的思想，大体过程分为两步：

• 分：将数组一分为二为两部分，一直分解到数组的长度为 1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」；

• 治：将两个较短的「有序数组」合并成一个长的有序数组，一直合并到最初的长度。

class Solution {
public:
    vector<int> tmp;
    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];//从0开始计数
    }
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

归并排序与逆序对统计

算法思路

在归并排序中统计逆序对的数量是非常经典的应用。主要就是在归并排序的合并过程中统计逆序对的数量，也就是合并两个有序序列的过程中，快速找出逆序对的数量。

我们将这个问题分解成几个小问题，逐一破解：

1. 默认都是升序：如果掌握升序的话，降序的归并过程也是可以解决的。

2. 先解决第一个问题：为什么可以利用归并排序？

   • 逆序对中两个元素：全部从左数组中选择

   • 逆序对中两个元素：全部从右数组中选择

   • 逆序对中两个元素：一个选左数组另一个选右数组

根据排列组合的分类相加原理，三种情况下产生的逆序对的总和，正好等于总的逆序对数量。

我们然后也在一左一右也在后面加排序！

归并排序的过程

归并排序的过程分为两步：

1. 分：将数组一分为二，一直分解到数组的长度为1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」；

2. 治：将两个较短的有序数组合并成一个长的有序数组，一直合并到最初的长度。

解决第二个问题

在归并排序合并的过程中，我们得到的是两个有序的数组。我们可以利用数组的有序性，快速统计出逆序对的数量，而不是将所有情况都枚举出来。

方法一：快速统计出某个数前面有多少个数比它大

通过一个示例来演示方法二：

假定已经有两个已经有序的序列以及辅助数组 left=[5,7,9] right=[4,5,8] help=[]，通过合并两个有序数组的过程，来求得逆序对的数量。

示例过程

1. 第一轮循环：

   • left[cur1] > right[cur2]，将 right[cur2] 加入到辅助数组中去，cur2++ 遍历下一个元素。

   • ret = 3，cur1 = 3 cur2 = 1

2. 第二轮循环：

   • left[cur1] == right[cur2]，将 left[cur1] 放入到辅助数组中去，cur1++ 遍历下一个元素。

   • ret = 3 cur1 = 4 cur2 = 1

3. 第三轮循环：

   • left[cur1] > right[cur2]，将 right[cur2] 加入到辅助数组中去，cur2++ 遍历下一个元素。

   • ret = 5 cur1 = 4 cur2 = 2

4. 第四轮循环：

   • left[cur1] < right[cur2]，将 left[cur1] 这个元素加入到辅助数组中去，不要细 ret 的值。

   • ret = 6 cur1 = 2 cur2 = 2

5. 第五轮循环：

   • left[cur1] < right[cur2]，与第一、第二、第三轮循环相同。此时 left 数组中的 1 个元素被与 right[cur2] 做逆序对，更新 ret 的值，并且将 right[cur2] 加入到辅助数组中去。

   • ret = 8 cur1 = 1 cur2 = 2

处理剩余元素

1. 如果是左边出现剩余：

   • 说明左边剩下的所有元素都是比右边元素大的，但是相较于方法二，逆序对的数量是没有统计的。因此，我们需要统计 ret 的值。

   • 设左边数组剩余元素的个数为 left，ret += leave - (cur2 - 0)

2. 如果是右边出现剩余：

   • 说明右边剩下的所有元素都是比左边元素大的，但是它们都是已经统计过的（我们以左边的元素为基准的），因此不会产生新的逆序对，仅需归并排序即可。

总结

整个过程只需将两个数组遍历一遍即可，时间复杂度依旧为 O(N)。

由上述过程我们可以得出方法一统计逆序对的关键点：

• 在合并有序数组的时候，遇到左数组当前元素 <= 右数组当前元素时，我们可以通过计算右数组已经遍历过的元素的数量，快速求出去数组当前元素后面有多少个数比它大。

升序：找到该数之前，有多少个元素比我大

降序：找到该数之后，有多少个元素比我小

我们假设降序也是采用上面的策略，当 nums[cur1] > nums[cur2] 了，就需要 ret += [left, cur1]，然后cur1++后，如果还是nums[cur1] > nums[cur2]，cur2不动，就会导致前面的部分重复计算了！

class Solution {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        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 = left + ((right - left) >> 1);
        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 j = left; j <= right; ++j) nums[j] = tmp[j - left];
        return ret;
    }
};

我们其实改成降序的版本也是ok的！（自行实现）

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

归并排序中的逆序对统计

算法思路

在归并排序中统计逆序对数量是一种经典的应用。此算法不仅要求总的逆序对数量，还需返回每个元素右边有多少个元素比它小。由于元素下标在归并过程中会变化，因此需要一个辅助数组来记录下标。

算法流程

1. 创建两个全局数组：

   • vector<int> index：记录下标

   • vector<int> ret：记录结果

   • index 用来与原数组中对应位置的元素绑定，ret 用来记录每个位置统计出来的逆序对的个数。

2. countSmaller() 主函数：

   • 计算数组 nums 的大小为 n。

   • 初始化定义的两个全局数组。

   • 调用 mergeSort() 函数，并返回 ret 结果数组。

3. mergeSort() 函数：

   • 修改全局变量 ret，统计出每个位置对应的逆序对的数量，并且排序。

   • 无需返回值，因为直接对全局变量修改。

4. mergeSort() 函数流程：

   • 定义递归出口：left >= right 时，直接返回。

   • 划分区间：根据 mid 将区间划分为 [left, mid] 和 [mid + 1, right]。

   • 统计左右两个区间逆序对的数量。

   • 合并左右两个有序区间，并统计出逆序对的数量。

合并有序区间

1. 创建两个大小为 right - left + 1 的辅助数组：

   • numsTmp：排序用的辅助数组。

   • indexTmp：处理下标用的辅助数组。

2. 初始化遍历数组的指针：

   • cur1 = left（遍历左半部分数组）

   • cur2 = mid + 1（遍历右半部分数组）

   • dest = 0（遍历辅助数组）

3. 循环合并区间：

   • 当 nums[cur1] <= nums[cur2] 时：

     • indexTmp[dest] = index[cur1]

     • ret[index[cur2]] += nums[cur1] - nums[cur2] + 1

     • cur1++

   • 当 nums[cur1] > nums[cur2] 时：

     • indexTmp[dest] = index[cur2]

     • cur2++

   • dest++

4. 处理剩余元素：

   • 如果左边有剩余，直接归并。

   • 如果右边有剩余，直接归并。

5. 将辅助数组的内容替换到原数组中。

当前元素的后边，有多少元素比我小？

当前元素的后边，有多少元素比我小？

当前元素的后边，有多少元素比我小？

class Solution {
public:
    vector<int> index;
    vector<int> ret;
    int tmpNums[500010];
    int tmpIndex[500010];
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n, 0);
        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 - left) >> 1);
        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];
        }
    }
};

493. 翻转对 - 力扣（LeetCode）

归并排序求解翻转对数量

算法思路

大思路与求逆序对的思路一样，就是利用归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：左半区间翻转对的数量，右半区间翻转对的数量，一左一右选择时翻转对的数量。重点就是在合并区间过程中，如何计算出翻转对的数量。

与上个问题不同的是，上一道题我们可以一边合并一边计算，但是这道题要求的是左边元素大于右边元素的两倍，如果我们直接合并的话，是无法快速计算出翻转对的数量的。

因此我们需要在归并排序之前完成翻转对的统计。

示例过程

下面依旧以一个示例来模仿两个有序序列如何快速求出翻转对的过程：

假定已经有两个已经有序的序列 left = [4, 5, 6] right = [1, 2, 3]。

用两个指针 cur1 cur2 遍历两个数组。

• 对于任意给定的 left[cur1] 而言，我们不断地向右移动 cur2，直到 left[cur1] <= 2 * right[cur2]。此时对于 right 数组而言，cur2 之前的元素全部都可以与 left[cur1] 构成翻转对。

• 随后，我们再将 cur1 向右移动一个单位，此时 cur2 指针并不需要回退（因为 left 数组是升序的）依旧往右移动直到 left[cur1] <= 2 * right[cur2]。不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对数目。

由于两个指针最后都是不回退的扫描到数组的结尾，因此两个有序序列求出翻转对的时间复杂度是 O(N)。

综上所述，我们可以利用归并排序的过程，将求一个数组的翻转对转换成求左数组的翻转对数量 + 右数组中翻转对的数量 + 左右数组合并时翻转对的数量。

class Solution {
public: 
    int tmp[50010];
    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return 0;
        int ret = 0;
        int mid = left + ((right - left) >> 1);
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if(cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }
        cur1 = left, cur2 = mid + 1;
        int i = 0;
        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 j = left; j <= right; ++j)
        {
            nums[j] = tmp[j - left];
        }
        return ret;

    }
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};