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
这道题跟LeetCode上的那道Count of Smaller Numbers After Self是一样的，唯一的一点点的小区别是那道题是返回一个向量，表示出原数组中每一个数字的右边比其小的数的个数，而这道题让我们求翻转对的总数，其实就是把每个数字右边比其小的数的个数都加起来即可，具体讲解请参加之前那篇博客Count of Smaller Numbers After Self，参见代码如下；
class Solution { public: long long reversePairs(vector<int>& A) { long long res = 0; vector<int> v; for (int i = A.size() - 1; i >= 0; --i) { int left = 0, right = v.size(); while (left < right) { int mid = left + (right - left) / 2; if (A[i] > v[mid]) left = mid + 1; else right = mid; } v.insert(v.begin() + right, A[i]); res += right; } return res; } };
本文转自博客园Grandyang的博客，原文链接：翻转对[LintCode] Reverse Pairs ，如需转载请自行联系原博主。
