题目描述

在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数。

样例
输入:[1,2,3,4,5,6,0]
输出:6

参考:https://www.bilibili.com/video/BV1Hv41167ft?from=search&seid=2747792850762973218

归并排序的典型应用
思路: 如果是从小到大的有序数组,是不存在逆序对的,产生逆序对的一定是无序或者递减的
无序变有序的过程就是将逆序对的两个元素进行交换,从而消灭逆序对
所以把交换的次数数出来,就是逆序对的个数
最简单的是冒泡(冒泡排序会进行逆序对的交换),但是时间复杂度高
用归并来实现排序。

在基础归并上加了一个句30行的:count+=(mid-i+1)
也就是左边子列的i大于右边子列j时候,由于左边是递增排序的,说明左边i之后的数字都大于j
所以逆序对就是左边子列i之后的元素的个数,就是mid-i+1

class Solution {
public:
    void merge(vector<int>& nums,int left,int right){
        if(left>=right) return;
        int mid=left+(right-left)/2;
        merge(nums,left,mid);
        merge(nums,mid+1,right);
        sort2vector(nums,left,mid,right);
        //left是左边子列开头,mid是左边子列结尾;mid+1是右边子列开头,right是右边子列结尾
    }
    void sort2vector(vector<int>& nums,int left,int mid,int right){

        int i=left,j=mid+1;
        int len=right-left+1;
        while(i<=mid&&j<=right){    
            if(nums[i]<=nums[j]) 
                ans.push_back(nums[i++]);
            else{
                count+=(mid-i+1);//对于[5 7] [4 6] 5>4,所以左边都大于4,count+2;
                ans.push_back(nums[j++]);
            } 
        }
        while(i<=mid)  ans.push_back(nums[i++]);
        while(j<=right)  ans.push_back(nums[j++]);
        for(int i=0;i<len;i++)
            nums[i+left]=ans[i];//ans是从0开始,但是nums从left开始
        ans.clear();
    }
    int reversePairs(vector<int>& nums) {
        merge(nums,0,nums.size()-1);
        return count;
    }
private:
    int count=0;
    vector<int> ans;  //把暂存的vector定义外面,每次用完clear,用时会少
};