原题
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;
}
};
