【剑指】45，数组中的逆序对

朱雀 2023-07-12 09:12 5阅读 0赞

**题目描述**  
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007  
输入  
1,2,3,4,5,6,7,0  
输出  
7  
**思路：**  
利用归并排序，从分组的末尾开始比较，如果前面的最后一个数大了，那么后面的那个index以及之前的全部是和前面这个index 的逆序对。while结束后还要将剩下的前堆/后堆放入辅助数组。  
代码：

class Solution { 
    public:
        int InversePairs(vector<int> data) { 
    	int length=data.size();
    	if(length==0)	
            return 0;
        return  getCount(data, 0,length-1);
        }
        int getCount(vector<int>& data, int begin,int end){ 
            if(begin>=end)
                return 0;       //递归终止
            int mid=(begin+end)/2;
            int lCount=getCount(data, begin, mid);
            int lCount=getCount(data, mid+1, end);
    
            int froIndex=mid, lastIndex=end, backIndex=end;
            int curCount=0;
            vector<int> tmpOfInv(data.size(), 0);
    
            while(froIndex>=begin && backIndex>=mid+1){ 
                if(data[froIndex]>data[backIndex] ){ 
                    tmpOfInv[lastIndex--]=data[froIndex--];
                    curCount+=backIndex-mid;
                }
                else{ 
                    tmpOfInv[lastIndex--]=data[backIndex--];
                }
            }
            while(froIndex>=begin){ 
                tmpOfInv[lastIndex--]=data[froIndex--];
            }
             while(backIndexIndex>=mid+1){ 
                tmpOfInv[lastIndex--]=data[backIndex--];
            }
            for(int i=begin;i<=end;++i)
                data[i]=tmpOfInv[i];
            return (lCount+rCount+curCount);
        }
    };