📃 题目描述

题目链接：剑指 Offer 51. 数组中的逆序对 (opens new window)

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

示例 1:

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

🔔 解题思路

题意是不要求这个逆序对是连续的

暴力 TODO

归并排序

只需要在标准的数组归并排序的基础上稍微加一点代码就行

合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」

详细动态图可参考 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/

class Solution {
    
    // 非常奇怪，LeetCode 上面这里要是用 static 修饰输出结果就会出错
    private int count = 0;
    
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return count;
        }

        mergeSort(nums, 0, nums.length - 1);

        return count;
    }

    private void mergeSort(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);
        // merge nums[left, mid] 和 nums[mid + 1, right] 两个数组
        merge(nums, left, right);
    }

    private void merge(int[] nums, int left, int right) {
        int[] temp = new int[right - left + 1];
        int index = 0;

        int mid = left + ((right - left) >> 1);

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

        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                temp[index ++] = nums[j ++];
                // nums[i..mid] 都可以和 nums[j] 组成逆序对
                count += mid - i + 1;
            }
            else {
                temp[index ++] = nums[i ++];
            }
        }

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

        // 将排序后的元素填充到数组 nums 中
        for (int k = 0; k < temp.length; k ++) {
            nums[left + k] = temp[k];
        }
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：