从零学算法（LCR 170）

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

• 第一反应肯定暴力解法 n 重循环了，那就算了。逆序对这个概念，其实你好好想想，和归并排序真的有很大的关联。同样分为前后部分，然后前后两部分做处理。也就是说，在归并排序合并左右数组的过程中，其实就会产生若干逆序对（左数组元素相对右数组元素，每一组都是逆序对），那还说什么，排序的归并过程其实就能统计逆序对，即排序完毕则统计完毕（归并排序可以参考我之前的学习笔记）。

•   int[] record, tmp;
    public int reversePairs(int[] record) {
        this.record = record;
        tmp = new int[record.length];
        return mergeSort(0, record.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分，m 其实就是左数组右边界
        int m = (l + r) / 2;
        // 合并统计结果
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = record[k];
        for (int k = l; k <= r; k++) {
        	// 如果左数组合并完了就直接用右数组
            if (i == m + 1)
                record[k] = tmp[j++];
            // 如果右数组用完了，或者左数组当前数更小（升序排序，所以取更小的）
            // 就取左数组的数
            else if (j == r + 1 || tmp[i] <= tmp[j])
                record[k] = tmp[i++];
            else {
                record[k] = tmp[j++];
                // 统计逆序对，此时说明左右数组都有数，并且左数组当前数大于右数组当前数
                // 左数组也是升序的，即之后的数也都大于右数组当前数，
                // 所以左数组当前范围比如为 [2,4]
                // 逆序对数量就是 4-2+1 有三个数
                res += m - i + 1; 
            }
        }
        return res;
    }
  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