【剑指Offer】（数组）数组中的逆序对（归并排序）

桃扇骨 2022-03-15 05:06 186阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_96bd6684e04a44eb80e6a68efc0ec6c5_tpId_13_tqId_11188_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

#### 解决方法 ####

class Solution { 
        int cnt=0;
    public:
        int InversePairs(vector<int> data) { 
            //归并排序的改进
            if(data.size()<=1) return cnt;
            MergeSort(data,0,data.size()-1);
            return cnt%1000000007;
        }
    
    
    void MergeSort(vector<int>& data,int left,int right){ 
    	if(left<right){ 
    		int mid=(left+right)/2;
    		MergeSort(data,left,mid);//分治 
    		MergeSort(data,mid+1,right);
    		Merge(data,left,mid,right); //归并 
    	} 
    }
            
    void Merge(vector<int>& data,int left,int mid,int right){ 
    	//对data[left,mid]和data[mid+1,right]进行归并
    	vector<int> data1(data.begin()+left,data.begin()+mid+1);
    	vector<int> data2(data.begin()+mid+1,data.begin()+right+1);
    	
    	int len1=mid-left+1, len2=right-mid,i,j,k;	
    	for(i=0,j=0,k=left;k<right;k++){ 
    		if(i==len1 || j==len2) break;
    		if(data1[i]<=data2[j]) data[k]=data1[i++];
    		else { 
                data[k]=data2[j++];	
                if(cnt>=1000000007) cnt%=1000000007;
                cnt+=(len1-i); //此题只比归并排序多了此行！！！
            }
    	}
        while (i<len1) data[k++]=data1[i++];
    	while (j<len2) data[k++]=data2[j++];
    }
        
    };

[https_www.nowcoder.com_practice_96bd6684e04a44eb80e6a68efc0ec6c5_tpId_13_tqId_11188_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking