逆序对数量

给定一个数组，统计数组中逆序对的数量

逆序对：下标和对应值的大小关系相反，例如 a[1] = 5, a[2] = 3，那么就构成一组逆序对

暴力求解

1
2
3
4
5
6
7
8
9
public int reversePairs(int[] a) {
    int res = 0, n = a.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[i]) res++;
        }
    }
    return res;
}

归并排序，主流求解

在归并排序归并的过程中，如果遇见左子数组的某个值大于了右子数组的对应值，那么从左子数组当前位置到最后，与右子数组的当前值均构成逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int reversePairs(int[] a) {
        int[] t = new int[a.length];
        return merge(a, 0, a.length - 1, t);
    }
    private int merge(int[] a, int l, int r, int[] t) {
        if (l >= r) return 0;
        int m = (l + r) >> 1;
        int res = merge(a, l, m, t) + merge(a, m + 1, r, t);
        System.arraycopy(a, l, t, l, (r - l + 1));
        int p1 = l, p2 = m + 1;
        for (int p3 = l; p3 <= r; p3++) {
            if (p1 == m + 1) a[p3] = t[p2++];
            else if (p2 == r + 1 || t[p1] <= t[p2]) a[p3] = t[p1++];
            else {
                a[p3] = t[p2++];
                res += (m - p1 + 1);
            }
        }
        return res;
    }
}

注意一下这里归并排序的写法，可以省略之前的三个循环，意义还是一样的