原题

LintCode 532. Reverse Pairs

Description

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.
return total of reverse pairs in A.

Example

Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3

解题

题意是找到一个数组中所有的逆序对的数量。

我们先思考一个情况，假设数组为[2,4,1,3,5]，那么此时我们考虑将数组随意分割为A、B两个有序部分[2,4]和[1,3,5]，并假设一个名为Sorted的缓冲区。分配的A、B必须满足一个条件就是有序，这个条件如何满足我们之后再讲。

首先我们可以确认的是，如果这个数组内没有任何逆序对，也就是说这个数组是有序（从小到大）的，那么必然存在的情况是，分片A中的所有值都小于分片B中的所有值。

此时，我们取两个分片第一个元素中的最小值，如果是A中的值，那么直接加入缓存区Sorted中。如果是B中的值，则说明这个值乱序了。那么因为这个值乱序，导致了多少个乱序对的产生呢？以刚刚的例子，第一次取到的最小值是分片B中头部数字1，很明显我们知道此事因为1产生的乱序对分别为(2,1) 和 (4,1)，即分片A中所有还存在的元素都能与这个数字组成乱序对。

那么我们只要持续上述过程，每次都从两个分片的头部取出较小的值，加入缓存区Sorted，如果这个值来自分片B，则乱序对总数量增加分片A中剩余的元素的个数。

那么下一个问题就是，如何保证分片A、B都是有序地呢？我们可以发现，在进行上面的操作时，其实相当于归并排序中的并的过程。那么我们实际上只需要多数组进行归并排序，每次并的时候都进行乱序对的统计即可。这样就可以保证分片A、B（实际上是归并排序中对半分出来的两个分片）是有序的。

代码

class Solution {
public:
    /*
    * @param A: an array
    * @return: total of reverse pairs
    */
    long long reversePairs(vector<int> &A) {
        // write your code here
        return mergeSort(A, 0, A.size() - 1);
    }
private:
    long long mergeSort(vector<int> &A, int start, int end) {
        if (start >= end) return 0;
        long long sum = 0;
        int mid = (start + end) / 2;
        sum += mergeSort(A, start, mid);
        sum += mergeSort(A, mid + 1, end);
        sum += merge(A, start, mid, end);
        return sum;
    }
    long long merge(vector<int> &A, int start, int mid, int end) {
        int left = start;
        int right = mid + 1;
        vector<int> temp;
        long long sum = 0;
        while (left <= mid && right <= end) {
            if (A[left] <= A[right]) {
                temp.push_back(A[left++]);
            } else {
                temp.push_back(A[right++]);
                sum += mid - left + 1;
            }
        }
        while (left <= mid) temp.push_back(A[left++]);
        while (right <= end) temp.push_back(A[right++]);
        for (int i = 0; i < temp.size(); i++)
            A[i + start] = temp[i];
        return sum;
    }
};