【分治算法】Leetcode编程题解：493. Reverse Pairs Add to List

Given an array nums, we call (i, j) an important reverse pair ifi < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

class Solution {public:     vector<long>::iterator find(vector<long>& tmp,long aim)     {         int a=0,b=tmp.size()-1;         while(a<b)         {             int c=(a+b)/2;             if(tmp[c]>aim)                b=c-1;             else if(tmp[c]<aim)                a=c+1;            else                 return tmp.begin()+c;         }         return tmp.begin()+a;     }     int count(vector<long>& tmp,int a)     {         int begin=0,end=tmp.size()-1,middle;         if(end<0)            return 0;         while(begin<end)         {             middle=(begin+end)/2;             if(tmp[middle]<a)                begin=middle+1;             else                end=middle;         }         if(tmp[begin]>=a)             return begin;         else            return tmp.size();     }    int reversePairs(vector<int>& nums) {        int n=nums.size();        vector<long >tmp(n,0);        for(int i=0;i<n;i++)            tmp[i]=(long )nums[i]*2L;        int ans=0;        sort(tmp.begin(),tmp.end());        for(int i=0;i<n;i++)        {            long aim=(long)nums[i]*2L;            vector<long>::iterator iter=find(tmp,aim);              tmp.erase(iter);            ans+=count(tmp,nums[i]);        }        return ans;    }};但是超时，所以参考已通过的代码，采用归并排序解决，以下为摘抄：Just a mergesort solution, but using iterators (instead of indexes) and inplace_merge.
class Solution {public:    int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) {        if (end - begin <= 1)            return 0;        auto mid = begin + (end - begin) / 2;        int count = sort_and_count(begin, mid) + sort_and_count(mid, end);        for (auto i = begin, j = mid; i != mid; ++i) {            while (j != end and *i > 2L * *j)                ++j;            count += j - mid;        }        inplace_merge(begin, mid, end);        return count;    }    int reversePairs(vector<int>& nums) {        return sort_and_count(nums.begin(), nums.end());    }};