题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
解题
方法一：暴力循环（超时）
class Solution { public: int reversePairs(vector<int>& nums) { int n=nums.size(); int res=0; for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(nums[i]>nums[j]) res++; } } return res; } };
方法二：归并排序
归并排序就是利用分治+归并的思想，将大问题用小问题分治去解决。
归并过程就是相当于合并两个有序数组
先将原始数组赋值给辅助数组
然后去修改原始数组。
将数组对半分，如果tmp[i]>tmp[j]，如下图，左侧有4个数比其大，因此逆序数为4,所以res+=4
此时tmp[i]
因此只有辅助数组中右侧，tmp[j]
class Solution { public: int reversePairs(vector<int>& nums) { vector<int> tmp(nums.size()); return mergeSort(0,nums.size()-1,nums,tmp); } private: int mergeSort(int l,int r,vector<int>& nums,vector<int>& tmp){ if(l>=r) return 0; //递归划分 int m=(l+r)/2; int res=mergeSort(l,m,nums,tmp)+mergeSort(m+1,r,nums,tmp); int i=1,j=m+1; //复制数组到辅助数组 for(int k=l;k<=r;k++){ tmp[k]=nums[k]; } //合并阶段 for(int k=l;k<=r;k++){ if(i==m+1) nums[k]=tmp[j++]; else if(j==r+1||tmp[i]<=tmp[j]) nums[k]=tmp[i++]; else{//tmp[i]>tmp[j]的情况 nums[k]=tmp[j++]; res+=m-i+1;//统计逆序对 } } return res; } };
