数据结构与算法 / 系统课时

用分治合并局部有序结果

用分治合并局部有序结果

有些数组问题既要求排序,又要求统计跨区间关系。直接枚举所有元素对通常是平方复杂度;分治可以先递归处理左右子区间,再利用“左右两边已经有序”这一条件,在一次线性合并中完成跨区间统计。

学习目标

  • 识别“拆成子区间、递归求解、合并结果”的分治结构
  • 理解有序子区间为什么能把跨区间统计降为线性扫描
  • 用归并过程实现逆序对计数并分析复杂度

把答案拆成三部分

以逆序对为例:若 i < j 且 nums[i] > nums[j],则 (i, j) 是一个逆序对。对区间 [left, right] 从中点拆开后,全部逆序对只可能属于三类:左半区内部、右半区内部、一个元素在左边而另一个在右边。

前两类可以交给递归处理。真正需要在当前层解决的只有第三类,也就是跨越中点的逆序对。关键条件是:递归返回时,让左右子区间同时保持有序。

分治统计逆序对的拆分与合并流程

在合并时批量计数

设左右两段已经分别有序,指针 i 指向左段当前元素,j 指向右段当前元素。

当 nums[i] <= nums[j] 时,左侧当前元素不会与右侧当前元素形成逆序对,可以正常写入结果。反过来,如果 nums[i] > nums[j],因为左半区已经有序,所以从 i 到 mid 的所有元素都大于 nums[j],可以一次增加 mid - i + 1 个逆序对,而不是逐个比较。

这正是分治加速的核心:先用递归制造局部有序性,再在合并阶段批量推导关系数量。

完整实现

下面的程序同时统计逆序对并把原数组排好序。临时数组只创建一次,在所有递归层复用,避免每次合并都重新申请大数组。

java
import java.util.Arrays;

public class Main {
    private static long sortAndCount(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        long count = sortAndCount(nums, temp, left, mid)
                + sortAndCount(nums, temp, mid + 1, right);

        int i = left;
        int j = mid + 1;
        int k = left;

        // 两个子区间都已排序,因此可以一次统计一批跨区间逆序对。
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                count += mid - i + 1L;
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        for (int p = left; p <= right; p++) {
            nums[p] = temp[p];
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 3, 5};
        int[] temp = new int[nums.length];
        long count = sortAndCount(nums, temp, 0, nums.length - 1);

        System.out.println(count);
        System.out.println(Arrays.toString(nums));
    }
}

预期输出

text
3
[1, 2, 3, 4, 5]

三个逆序对分别是 (2, 1)、(4, 1) 和 (4, 3)。最终数组有序并不是额外目标,而是下一层合并能够快速统计跨区间关系的前提。

复杂度与常见边界

递归树共有 O(log n) 层,每一层的所有合并操作总共扫描 O(n) 个元素,因此时间复杂度为 O(n log n)。临时数组需要 O(n) 空间,递归调用栈需要 O(log n) 空间。

合并条件应写成 nums[i] <= nums[j]。相等元素不属于逆序对,如果误写成严格小于,就会把相等值错误计入答案。计数变量还应优先使用 long:当数组很长且接近降序时,逆序对数量可能远大于 int 能安全表示的范围。

这种套路不只用于逆序对。只要目标关系能够被拆成“左区间答案 + 右区间答案 + 跨区间答案”,并且局部有序性可以帮助快速计算第三部分,就值得考虑分治归并,而不是直接枚举所有元素对。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用分治合并局部有序结果

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通