题目链接-来源：力扣（LeetCode）

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

示例 1:

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

思路：

有一个基础知识：排序算法的本质就是不停寻找数组中的逆序对，然后一个个交换消灭之。那么我们只要用一个复杂度较低 O(nlong) 且每一步排序交换一组逆序对的排序算法为载体，每次交换时计数一次逆序对，最终返回值即是我们需要的逆序对的总数。
这里自然想到用「归并排序」为载体（注意，O(nlogn)复杂度的排序方法很多，堆排序每次维护最小堆时的交换步骤也可用来计数；快速排序由于其无序性，每次划分可能会一次性消灭很多对逆序对，不方便统计）。
现在我们仔细思考，每次「交换」操作，跟逆序对的具体数量关系如何。首先，某一轮归并排序的输入是两个有序的数组，记为 A[]，B[]。指针 pA 指向 A[] 开头， pB 指向 B[] 开头。当我们进行若干次归并以后，pA = i，pB = j。
假设 A[i] <= B[j] ，则我们要添加 A[i] 进入归并序列，同时 pA++。考察关于 A[i] 的逆序对数量，我们可以有如下的信息和推论：

  • 我们默认 A[] 的所有元素目前都在 B[] 的「左侧」（也就是完成排序后较小元素所在的那一侧）
  • 在 A[] 和 B[] 内部逆序对的数量为0（两个数组已经分别有序），也就是对于 A[i]，我们不需要考虑 A[] 中任何元素，只需要考虑 B[]
  • 我们的取数策略（从小到大取数），导致：我们当前取到的元素（A[i]）大于等于任何已取到的元素（A[i - 1] 及之前的元素，B[j] 及之前的元素）、同时小于等于任何未取到的元素
    对于我们要取出的 A[i]，有 A[i] <= B[j]，也就是 B[j] 及以后元素**应该**排在A[i] 的右侧，且**将会**排在 A[i] 的右侧，因此只需考虑 B[j - 1] 及其之前元素。对于这部分元素，严格有 A[i] > B[j - 1]，即「 A[i] 应该在 B[j - 1] 等元素的右侧」，且由于所有的 A[] 中元素一开始都在 B[] 中元素左侧，所以 B[j - 1] 到 B[0] 这部分元素的个数 j ，就是 A[i] 对应的逆序对个数。
    注意，我们总是可以只统计某一侧数组的逆序对（比如只关心 A[]），而不用考虑另一侧。这是因为逆序对总是成对出现的，并且数组内部有序保证了内部逆序对的个数为 0，因此逆序对的元素一定是分别出现在 A[]、B[] 当中，我们只需以其中一个数组为准进行统计即可。
    时间复杂度：O(nlogn)
    空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        return mergeCount(nums, 0, n - 1);
    }
    private int mergeCount(int[] arr, int start, int end) {
        if (start == end) {
            return 0;
        }
        int i = start;
        int mid = start + (end - start) / 2;
        int j = mid + 1;
        int count = mergeCount(arr, start, mid) + mergeCount(arr, mid + 1, end);
        int [] tmp = new int[end - start + 1];
        int k = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
                count += j - mid - 1;
            } else {
                tmp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
            count += j - mid - 1;
        }
        while (j <= end) {
            tmp[k++] = arr[j++];
        }
        System.arraycopy(tmp, 0, arr, start, end - start + 1);
        return count;
    }
}