题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
输入例子:
1,2,3,4,5,6,7,0
输出例子:
7
解题思路:本题采用归并排序的思想。先将数组分解成长度为1的若干个数组,然后相邻的数组之间合并,并记录逆序对数目。得到left right
合并最后的两个数组,比较两数组的最后一位,大的放入辅助数组中,若左侧的大于右侧的,则右侧中的元素数目即为逆序对数目,进行count+,最后,把左侧或者右侧,剩余的元素也存入辅助数组。逆序对数目=count+left+right
1 class Solution { 2 public: 3 int InversePairs(vector<int> data) 4 { 5 int length = data.size(); 6 if(length <= 0) 7 return 0; 8 //定义辅助数组 9 vector<int> copy; 10 for(int i=0;i<length;i++) 11 { 12 copy.push_back(data[i]); 13 } 14 int count = InversePairsCore(data,copy,0,length-1); 15 16 return count; 17 } 18 int InversePairsCore(vector<int> &data,vector<int> ©,int start,int end) 19 { 20 //结束递归条件,只剩一个元素 21 if(start == end) 22 { 23 copy[start] = data[start]; 24 return 0; 25 } 26 int length = (end-start)/2; 27 int left = InversePairsCore(copy,data,start,start+length)%1000000007; 28 int right = InversePairsCore(copy,data,start+length+1,end)%1000000007; 29 30 //i初始化为前半段最后一个数字下标 31 int i = start+length; 32 //j吃书画问后半段最后一个数字下标 33 int j = end; 34 int indexCopy = end; 35 int count = 0; 36 while(i>=start && j>=start+length+1) 37 { 38 if(data[i]>data[j]) 39 { 40 copy[indexCopy--] = data[i--]; 41 count+=j-start-length;//右侧一共有j-start-length个元素,都小于data[i] 42 if(count >= 1000000007) 43 { 44 count %= 1000000007; 45 } 46 } 47 else 48 { 49 copy[indexCopy--] = data[j--];//右侧元素大不存在逆序对 50 } 51 } 52 for(;i>=start;i--) 53 { 54 copy[indexCopy--] = data[i]; 55 } 56 for(;j>=start+length+1;j--) 57 { 58 copy[indexCopy--] = data[j]; 59 } 60 61 return (left+right+count)%1000000007; 62 } 63 };