493. 翻转对

• 方法一

class Solution {
public:int reversePairs(vector<int>& nums) {return div(nums,0,nums.size()-1);}int div(vector<int> &nums,int l,int r){if(l>=r) return 0;int mid = l+(r-l)/2;int res = div(nums,l,mid)+div(nums,mid+1,r);// 合并int j = 0;for(int i=l;i<=mid;i++){while(j+mid+1<=r && (long)nums[i]>(long)2*nums[j+mid+1]){j++;}res += j;}vector<int> v(r-l+1);    int i = l;j = mid+1;int pos = 0; while(i<=mid && j<=r){if(nums[i]<=nums[j]) v[pos++] = ( nums[i++] );else v[pos++] = ( nums[j++] );}while(i<=mid) v[pos++] = ( nums[i++] );while(j<=r) v[pos++] = ( nums[j++] );pos = 0;for(i=l;i<=r;i++){nums[i] = v[pos++];}return res;   }
};

• 方法二

class BIT{
private:static const int N = 100010;int c[N] = {0};int lowbit(int x){return x&-x;}public:void update(int x){while(x<N){c[x]++;x += lowbit(x);}}int ask(int x){int res = 0;while(x){res += c[x];x -= lowbit(x);}return res;}};class Solution {
public:int reversePairs(vector<int>& nums) {set<long> st;for(long x:nums){st.insert(x);st.insert(2*x);}unordered_map<long,int> f;// 从1开始int index = 1;for(long x:st){f[x] = index++;}BIT bit;int ans = 0;for(long x:nums){int left = f[2*x];ans += bit.ask(index)-bit.ask(left);bit.update(f[x]);}return ans;}
};