【优选算法篇】分治乾坤，万物归一：在重组中窥见无声的秩序

本文深入探讨了归并排序的核心思想与进阶应用，围绕分治策略展开，从基础的数组排序到复杂的逆序对、翻转对和右侧更小元素计数，展示了归并排序在算法世界中的广泛应用。分治法通过“分而治之”的思想，将复杂问题拆解为更小的子问题，利用递归求解并合并结果，以高效优雅的方式完成任务。文章详细解析了归并排序的算法步骤，包括分区、排序、合并，同时通过实例讲解了在合并过程中统计复杂数量的技巧，如逆序对数量与翻转对的统计

Trouvaille ~

1493人浏览 · 2024-11-17 22:48:16

Trouvaille ~ · 2024-11-17 22:48:16 发布

分治专题（二）：归并排序的核心思想与进阶应用

🚀 欢迎讨论：如果您对内容有任何疑问或见解，欢迎在评论区留言。

👍 点赞、收藏与分享：如果觉得这篇文章对您有帮助，请点赞、收藏并分享给更多朋友。

💡 分享给更多人：一起学习分治策略，掌握归并排序的精髓！

前言、

上篇：【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术

归并排序是经典的分治法应用，其核心在于“分而治之”的思想。通过不断划分，将一个复杂问题逐步拆解成若干规模更小的子问题，以递归方式求解，再将解合并，从而解决初始问题。本文将围绕归并排序的基本原理，结合排序数组的题目，深入剖析归并排序在分治中的实际应用。

第二章：归并排序的应用与延展

2.1 归并排序（medium）

题目链接：912. 排序数组

题目描述：

给定一个整数数组 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]

解法（归并排序）

算法思路：

归并排序的过程充分体现了“分而治之”的思想，基本步骤分为以下两部分：

分：将数组一分为二，递归地继续分割，直到每个子数组的长度为 1，确保所有分块都已排序。
治：将两个已排序的子数组合并成一个有序数组，最终返回整个数组的有序结果。

具体步骤：

使用中间点将数组分成 [left, mid] 和 [mid + 1, right] 两部分。
递归对左右区间进行排序。
在排序好的左右子数组中，使用双指针将较小的元素依次合并到临时数组 tmp 中。
合并完成后，将 tmp 数组的内容拷贝回原数组。

C++ 代码实现

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; // 递归终止条件
        
        // 1. 分区
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        // 2. 合并两个已排序数组
        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++]; // 右边剩余部分
        
        // 3. 拷贝回原数组
        for (int j = 0; j < i; ++j) {
            nums[left + j] = tmp[j];
        }
    }
};

易错点提示

递归终止条件：
- 在 mergeSort 函数中，left >= right 时停止递归，以防止无穷递归导致的栈溢出。
合并逻辑：
- cur1 和 cur2 分别指向左、右子数组的起始位置，使用 tmp 存储合并结果。确保在所有元素都合并后，将 tmp 拷贝回 nums 中。
临时数组的使用：
- 临时数组 tmp 存储每一轮合并结果，以确保排序结果被完整保留到下一轮递归。

时间复杂度和空间复杂度

时间复杂度：O(n log n)。每轮合并的时间复杂度为 O(n)，分区深度为 log n。
空间复杂度：O(n)，临时数组 tmp 占用额外空间。

2.2 数组中的逆序对（hard）

题目链接：剑指 Offer 51. 数组中的逆序对

题目描述：

在一个数组中的两个数字，如果前面的一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1：

输入：[7,5,6,4]
输出：5

解法（利用归并排序的过程 — 分治）

算法思路：

归并排序求逆序数是经典的方法。在归并排序的合并过程中，我们可以顺便统计出逆序对的数量，这样可以避免暴力统计的 O(n^2) 时间复杂度。

逆序对的产生方式可分为三种情况：

左数组中的元素逆序。
右数组中的元素逆序。
左数组和右数组中的元素形成逆序。

归并排序过程可以分为两个步骤：

分：将数组一分为二，不断划分，直到每个子数组长度为1。
治：将左右子数组合并成一个有序数组的过程中，统计逆序对的数量。

核心步骤与实现细节

为什么可以利用归并排序求逆序对？

因为在归并排序的过程中，我们通过分治的方法将数组拆分成左右两部分。每部分内部的逆序对可以分别在排序的过程中统计。最终在归并左右数组时，可以统计那些横跨左右数组的逆序对，这三者相加即为总的逆序对数。
核心问题：如何在合并两个有序数组的过程中统计逆序对的数量？

在合并左右两个已排序的数组时，可以高效统计出横跨两个数组的逆序对数。考虑以下例子：

假设有两个有序序列 left = [5, 7, 9] 和 right = [4, 5, 8]。
目标是计算在合并的过程中 left 中的元素大于 right 中的元素的情况数量。
合并并统计逆序对的过程：

定义指针 cur1 遍历 left 数组，cur2 遍历 right 数组。
定义 ret 记录逆序对的数量，help 数组临时存储排序的结果。
- 第一轮：
  - 比较 left[cur1] 和 right[cur2]，如果 left[cur1] > right[cur2]，则意味着从 cur1 到末尾的元素都大于 right[cur2]（因为 left 是有序的）。我们可以确定逆序对数量并将结果累加到 ret。
  - 若 left[cur1] <= right[cur2]，则将 left[cur1] 添加到 help 数组中。
- 处理剩余元素：若一侧数组元素遍历完，剩余元素直接添加到 help 数组即可，不会再产生新的逆序对。

C++ 代码实现

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;
        // 1. 找中间点，将数组分成两部分
        int mid = (left + right) >> 1;

        // 2. 左、右部分的逆序对数量
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        // 3. 合并并统计逆序对数量
        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++];
            }
        }

        // 4. 处理剩余元素
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        
        // 5. 将 tmp 数组内容拷贝回原数组
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }

        return ret;
    }
};

易错点提示

递归终止条件：
- 当 left >= right 时，表示已将数组分割到单个元素，递归停止返回0。
统计逆序对：
- 当 nums[cur1] > nums[cur2] 时，说明 left[cur1] 及后面的所有元素都大于 right[cur2]，则这些元素与 right[cur2] 构成逆序对。统计并更新 ret 的值。
处理剩余元素：
- 若左数组或右数组有剩余，则直接将剩余部分加入到 tmp，因为剩余部分不会形成逆序对。
拷贝回原数组：
- 最后将 tmp 的排序结果拷贝回 nums，确保在递归的上一级合并时数组依旧有序。

时间复杂度和空间复杂度

时间复杂度：O(n log n)。归并排序的分治递归实现使得时间复杂度达到 O(n log n)。
空间复杂度：O(n)，需要额外的数组存储合并结果。

2.3 计算右侧小于当前元素的个数（hard）

题目链接：315. 计算右侧小于当前元素的个数

题目描述：

给你一个整数数组 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 个更小的元素。

解法（利用归并排序的过程 — 分治）

算法思路：

本题和求数组中的逆序对非常类似，但与逆序对的统计不同之处在于：

需要返回一个数组 counts，记录每个元素右侧更小的元素数量，而不是单一的逆序对总数。
归并排序过程中，除了排序，还需要记录排序过程中元素的索引位置的变化。

核心步骤

辅助数组和索引绑定：
- 定义一个 index 数组，用于记录元素对应的原始索引，确保元素与下标绑定在一起。
- ret 数组存储每个元素右侧更小元素的数量。
递归排序：
- 递归地对数组进行分治排序，并统计左右子数组中每个元素右侧更小的元素数量。
合并排序并统计逆序对：
- 当合并两个有序数组时，如果发现左侧的某个元素大于右侧的当前元素，则说明该左侧元素右侧的所有元素都小于它。将这些逆序对数量累加到对应的 ret 索引上。
- 同时，完成左右子数组的归并操作。

C++ 代码实现

class Solution {
    vector<int> ret;        // 结果数组
    vector<int> index;      // 记录元素的原始下标
    int tmpNums[100010];    // 临时数组用于排序
    int tmpIndex[100010];   // 临时数组用于记录索引排序

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n, 0);       // 初始化结果数组为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;

        // 1. 分区
        int mid = (left + right) / 2;

        // 2. 递归处理左右子区间
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 3. 合并并统计逆序对
        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];
        }
    }
};

易错点提示

确保索引正确绑定：
- 在每次合并的过程中，索引数组 index 也需要同步排序，以保证结果数组 ret 的统计准确。
统计逆序对的逻辑：
- 当 nums[cur1] > nums[cur2] 时，说明从 cur2 到 right 的所有元素都小于 nums[cur1]，需要将这些数量累加到 ret[index[cur1]]。
递归终止条件：
- 当 left >= right 时停止递归，避免无效操作。

时间复杂度和空间复杂度

时间复杂度：O(n log n)。分治递归的时间复杂度是 O(log n)，每次合并的时间复杂度是 O(n)。
空间复杂度：O(n)。需要额外的临时数组 tmpNums 和 tmpIndex 进行合并排序。

2.4 翻转对（hard）

题目链接：493. 翻转对

题目描述：

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。

示例 1：

输入：nums = [1,3,2,3,1]
输出：2

解法（归并排序 — 分治）

算法思路：

翻转对的统计与逆序对非常类似，都可以利用 归并排序 的思想，将问题分解为三部分：

左数组中的翻转对数量。
右数组中的翻转对数量。
左右数组合并时的翻转对数量。

由于翻转对要求的是 nums[i] > 2 * nums[j]，直接在合并排序时统计会比较困难，因此：

我们在归并排序前，提前统计 左右两部分数组中满足条件的翻转对数量。
在统计完成后，再进行归并排序。

核心步骤与实现细节

统计翻转对数量：
- 使用两个指针 cur1 和 cur2，分别遍历左、右子数组。
- 对于每个左数组元素 nums[cur1]，找到右数组中第一个不满足 nums[cur1] > 2 * nums[cur2] 的位置 cur2。
- 此时，cur2 - mid - 1 即为当前 cur1 的翻转对数量，累加到结果中。
合并两个有序数组：
- 合并时，按照归并排序的逻辑，将两个子数组排序，并写入临时数组。
递归分治：
- 每次划分数组为 [left, mid] 和 [mid + 1, right]，递归统计翻转对数量并排序。

C++ 代码实现

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;
        // 1. 分区
        int mid = (left + right) / 2;

        // 2. 递归计算左右区间的翻转对数量
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        // 3. 统计翻转对数量
        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur2] * 2 < nums[cur1]) {
                cur2++;
            }
            ret += cur2 - mid - 1;
            cur1++;
        }

        // 4. 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        int i = left;
        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 j = left; j <= right; j++) {
            nums[j] = tmp[j];
        }

        return ret;
    }
};

易错点提示

统计翻转对的逻辑：
- 必须确保 cur2 指针只向右移动，不会回退，避免重复计算。
- 注意翻转对的判断条件 nums[cur1] > 2 * nums[cur2]，需要考虑到浮点运算可能导致的精度问题，因此 2 * nums[cur2] 可能需要写成 nums[cur1] > 2LL * nums[cur2]。
归并排序的逻辑：
- 合并时，确保临时数组和原数组的元素同步，避免在递归的上一层出错。
边界条件：
- 单元素或空数组的递归终止条件是 left >= right。