一、題目描述

二、解題思路

本題的思路與逆序數的思路相似，采用歸并排序的思路來實現。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; }
};