题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
class Solution { public: void merge(vector<int>& nums,vector<int>& v,int left,int right,int mid,int& count) { int i=left,j=mid+1,k=0; while(i<=mid && j<=right) { if(nums[i] < nums[j]) { v[k++] = nums[i++]; } else { count = (count+(mid-i+1))%1000000007; v[k++]=nums[j++]; } } while(i<=mid) { v[k++] = nums[i++]; } while(j<=right) { v[k++]=nums[j++]; } k=0; while(left<=right) { nums[left++] = v[k++]; } } void mergsort(vector<int>& nums,vector<int>& v,int left,int right,int& count) { if(left == right) return; else{ int mid = left + ((right-left) >>1); mergsort(nums,v,left,mid,count); mergsort(nums,v,mid+1,right,count); merge(nums,v,left,right,mid,count); } } int InversePairs(vector<int>& nums) { // write code here int count=0, len=nums.size(); vector<int> v(len); mergsort(nums,v,0,len-1,count); return count; } };