一、题目描述

二、解题思路

本题的思路与逆序数的思路相似，采用归并排序的思路来实现。leetcode LCR 170.交易逆序对的总数-CSDN博客

注意：但是逆序数的ret更新在左、右区间合并时更新，但本题ret更新在左、右区间合并前更新。

三、代码实现

时间复杂度：T(n)=O(nlogn)

空间复杂度：S(n)=O(n)

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& nums) {//借助归并排序的思路tmp.resize(nums.size());return mergeSort(nums,0,nums.size()-1);}int mergeSort(vector<int>& nums,int left,int right){//递归出口if(left>=right) return 0;//1.寻找中间位置int mid=left+(right-left)/2;//2.左边寻找+左排序，右边寻找+右排序int ret=0;ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);//3.一左一右寻找翻转对int cur1=left,cur2=mid+1;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=2LL*nums[cur2])cur1++;else{ret+=mid-cur1+1;cur2++;}}//4.左右两路归并cur1=left,cur2=mid+1;int i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur1++];else tmp[i++]=nums[cur2++];}//5.处理没有归并完的部分while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];//6.还原nums数组for(int j=left;j<=right;j++)nums[j]=tmp[j-left];return ret; }
};