分治算法实战：归并排序与逆序对问题

一、归并排序

题目描述：

给定一个整数数组，将其排序。

题目解析：

• 就是排序数组。

解题思路：

• 分： 将数组一分为二为两部分，一直分解到数组的长度为 1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」；
• 治： 将两个较短的「有序数组合并成一个长的有序数组」，一直合并到最初的长度。

解题代码：

// 时间复杂度：O(NlogN)
// 空间复杂度：O(n)
class Solution {
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    // 归并排序
    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int left = l;
        int right = r;
        int mid = (left + right) / 2;
        // 分
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        // 治：合并两个有序数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] < nums[cur2]) tmp[i++] = nums[cur1++];
            else 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];
        }
    }
}

二、LCR170.交易逆序对的总数

题目描述：

计算数组中逆序对的总数。逆序对是指在该数组元素之后与比它小的元素组成的两个数字。

2.1 分治思想

解题思路：

• 两段子数组的逆序对和，我们可以通过递归实现。
• 核心是求一左一右选取逆序对的和。
• 直接遍历求解复杂度高，如果我们将两段子数组排序，就可以简化统计逻辑。
• 这与归并排序的逻辑类似。

降序排序：找后一个数组中小的元素个数即可（当 nums[cur2] < nums[cur1] 时统计），即 [mid+1, right]。如果求前一个数组大元素，会有重复。

升序排序：找前一个子数组中大的元素个数即可（当 nums[cur2] < nums[cur1] 时统计），即 [cur1, mid]。如果求后一个数组小元素，会有重复。

数组总逆序对和等于：两段子数组的逆序对和 + 前面一段数组中每个元素在后面一段元素组成的逆序对和（简称为一左一右选逆序对）。

解题代码：

// 时间复杂度：O(NlogN)
// 空间复杂度：O(n)
// 升序版本：
class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
        // 分：两段子数组的逆序对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 治：合并两个有序数组 + 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        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];
        return ret;
    }
}

// 降序版本：
class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
        // 分：两段子数组的逆序对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 治：合并两个有序数组 + 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur2++];
            else {
                ret += (right - cur2 + 1);
                tmp[i++] = 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];
        return ret;
    }
}

2.2 暴力枚举

解题思路：

• 直接两个 for 循环，第一层遍历数组，第二层遍历后续元素比该元素小的数组个数。
• 会超时。

解题代码：

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
    public int reversePairs(int[] record) {
        int ret = 0;
        for (int i = 0; i < record.length; i++) {
            for (int j = i + 1; j < record.length; j++) {
                if (record[i] > record[j]) ret++;
            }
        }
        return ret;
    }
}

三、315.计算右侧小于当前元素的个数

题目描述：

返回一个数组，其中第 i 个元素表示在原始数组中，位于索引 i 右侧且小于 nums[i] 的元素个数。

题目解析：

• 这道题跟上一题类似，但是需要记录下标对应的结果。
• 最后返回存个数的数组。

3.1 分治思想

解题思路：

• 思路与上一题一致，将数组分为两段。每个下标的数组对应值等于：前一段个数 + 后一段个数。
• 由于求小的个数，使用降序求法更直观，使用升序需考虑边界情况。
• 当 nums[cur2] < nums[cur1] 时统计 [mid+1, right] 个数，放入结果数组的 nums[cur1] 对应下标位置。
• 需要将数组中的值与其下标对应，由于数组中元素可以重复，不能使用哈希表。使用一个数组记录每个元素的下标，两个数组绑定，同时移动。
• 下标数组的移动和原数组的移动是一样的，所以合并时也需要引入临时数组。

解题代码：

// 时间复杂度：O(NlogN)
// 空间复杂度：O(n)
// 降序版本：
class Solution {
    int[] tmpNums;
    int[] tmpIndex;
    int[] ret;
    int[] index;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        tmpIndex = new int[n];
        tmpNums = new int[n];
        ret = new int[n];
        // 下标数组
        index = new int[n];
        for (int i = 0; i < n; i++) index[i] = i;
        mergeSort(nums, 0, n - 1);
        List<Integer> list = new ArrayList<>();
        for (int x : ret) list.add(x);
        return list;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        // 分：两段子数组
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 治：合并两个有序数组，下标数组同时合并 + 统计个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur2] >= nums[cur1]) {
                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];
            index[j] = tmpIndex[j];
        }
    }
}

3.2 暴力枚举

解题思路：

• 两层 for 循环即可。
• 会超时。

解题代码：

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int a = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) a++;
            }
            ret.add(a);
        }
        return ret;
    }
}

四、493.翻转对

题目描述：

计算数组中满足 i < j 且 nums[i] > 2 * nums[j] 的翻转对数量。

4.1 分治思想

解题思路：

• 依旧是将数组分为两段：数组的总翻转对和等于：两段子数组的翻转对和 + 前面一段数组中每个元素在后面一段元素组成的翻转对和（简称为一左一右选翻转对）。
• 依旧可以是分升序和降序来求：
  • 升序排序：立足 cur2，找前一个子数组中大的元素个数即可，即 [cur1, mid]。
  • 降序排序：立足 cur1，找后一个数组中小的元素个数即可，即 [mid+1, right]。
• 由于判断条件与合并是不一样的，所以单独写一个循环来计算。
• 每个元素不会超出 int 范围，但是乘 2 就有可能会超出，所以判断条件写 nums[cur1] / 2.0 <= nums[cur2]。

解题代码：

// 时间复杂度：O(NlogN)
// 空间复杂度：O(n)
// 升序版本：
class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
        // 分：两段子数组的翻转对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while (cur2 <= right) {
            while (cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;
            if (cur1 > mid) break;
            ret += (mid - cur1 + 1);
            cur2++;
        }
        // 治：合并两个有序数组
        cur1 = left; cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] < nums[cur2]) tmp[i++] = nums[cur1++];
            else 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];
        }
        return ret;
    }
}

// 降序版本：
class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
        // 分：两段子数组的翻转对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        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) {
            if (nums[cur1] < nums[cur2]) tmp[i++] = nums[cur2++];
            else tmp[i++] = 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];
        }
        return ret;
    }
}

4.2 暴力枚举

解题思路：

• 直接两层 for 循环即可。
• 会超时。

解题代码：

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
    public int reversePairs(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] / 2.0 > nums[j]) ret++;
            }
        }
        return ret;
    }
}