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.
Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3
Solution 1: the same as the leetcode question 315. Count of Smaller Numbers After Self
class Solution { public: /** * @param A an array * @return total of reverse pairs */ long long reversePairs(vector<int>& A) { // Write your code here long long res=0; vector<int> t; for (int i=A.size()-1;i>=0;i--){ int index=lower_bound(t.begin(),t.end(),A[i])-t.begin(); t.insert(t.begin()+index,A[i]); res+=index; } return res; } };
原文：http://www.cnblogs.com/anghostcici/p/7439922.html