当前位置：首页 > article >正文

(每日一道算法题)交易逆序对的总数

article 2025/3/22 13:24:15

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

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

提示：

0 <= record.length <= 50000

暴力解法的问题

最直观的解法是双重循环遍历所有可能的 (i, j) 组合，统计满足 i < j 且 record[i] > record[j] 的对数。这种方法的时间复杂度为 O(n²)，当数组长度较大（例如 50000）时，显然无法高效处理。

归并排序解法

归并排序的分治思想天然适合解决逆序对问题。在归并排序的合并阶段，可以高效地统计逆序对数目。

归并排序合并阶段的统计逻辑

分治：将数组分为左右两部分，递归处理左右子数组。
合并：合并两个有序子数组时，若左子数组的当前元素大于右子数组的当前元素，则左子数组中剩余的所有元素均与该右子数组元素构成逆序对。
累加：每次发现左子数组元素大于右子数组元素时，累加左子数组剩余元素的个数到总逆序对数目。

代码实现

class Solution {
    int[] tmp; // 临时数组用于归并排序
    int ret;   // 统计逆序对总数

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

    private void mergesort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        // 递归处理左右子数组
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        // 若左子数组最大值 <= 右子数组最小值，无需合并
        if (nums[mid] <= nums[mid + 1]) return;
        // 合并两个有序子数组，并统计逆序对
        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];
        }
    }
}

示例分析

以示例 record = [9, 7, 5, 4, 6] 为例，归并排序的合并过程如下：

初始分割：数组分为左 [9,7,5] 和右 [4,6]。
处理左子数组：
- 分割为 [9,7] 和 [5]，合并时 9 > 7 产生 1 个逆序对。
- 合并 [7,9] 和 [5]，7 > 5 产生 2 个逆序对。
处理右子数组：合并 [4] 和 [6]，无逆序对。
合并左右子数组：
- 比较 5 和 4，产生 3 个逆序对。
- 比较 5 和 6，无逆序对。
- 比较 7 和 6，产生 2 个逆序对。
- 累计总逆序对数目为 1 + 2 + 3 + 2 = 8。